|
发表于 2020-10-9 16:59:28
|
显示全部楼层
首先我觉得这个问题就不太严谨 ,(只是用来练习new 、delete的 似乎也不需要很严谨)
以下代码都是建立在 我认为题目的意思是 “求两个字符串的最长公共子串 ,并随机返回其中一个”的基础上的
用的枚举的算法,时间复杂度O(n3) ,效率极低,想高效率还得用正经算法(这里没必要,况且咱也不会 )。
- //求两个字符串的最长公共子串 ,并随机返回其中一个
- char* get_same_string(char* p1, char* p2) {
- int maxLen = 0; //最长子串长度
- char* maxIndexp = NULL; //记录最长子串在p1中对应的起始地址
- int curLen = 0; //本轮子串长度
- int p1Len = strlen(p1);
- int p2Len = strlen(p2);
- for (int i1 = 0; i1 < p1Len; ++i1) { //p1
- for (int i2 = 0; i2 < p2Len; ++i2) { //p2
- curLen = 0;
- while ((p1[i1 + curLen] != 0) && (p1[i1 + curLen] == p2[i2 + curLen])) { //首先保证数组不越界
- ++curLen;
- }
- if (curLen > maxLen) {
- maxLen = curLen;
- maxIndexp = p1 + i1;
- }
- }
- }
- if (maxLen == 0)
- return NULL;
- char* pSameString = new char[maxLen + 1];
- memset(pSameString, 0, maxLen + 1); //清空
- memcpy(pSameString, maxIndexp, maxLen); //复制
- return pSameString;
- }
- int main()
- {
- char p1[] = "aabbcc";
- char p2[] = "kkbcyy";
- char* pSameString = get_same_string(p1, p2);
- cout << pSameString << endl;
- delete[] pSameString;
- return 0;
- }
复制代码 |
|