输入字符串中对称的子字符串的最大长度。比如输入字符串“roorle”,由于该字符串里最长的对称子字符串是“roor”,因此输出4.
(1)用代码实现方法;
(2)设计并写出测试用例,测试自己所实现的方法;
(3)请给出编程时容易出现的bug现象,原因;
(4)有无其他实现方法(说明思路即可),比较这两种实现方法优劣,以及各自容易产生的bug有什么不同?
思路: (1)将字符串str1="roorle"反序为str2 = "elroor" (2)求str1和str2的最大公共子串 //求两个字符串的最大子串长度 int findMaxSubstr(const char* str1, const char* str2) { if (str1 == NULL || str2 == NULL) { return 0; } int max = 0; int len1 = strlen(str1); int len2 = strlen(str2); int** dp = new int*[len2]; for (int i=0; i<len2; i++) { dp[i] = new int[len1]; } for (int i=0; i<len2; i++) { if (str1[0] == str2[i]) { dp[i][0] = 1; } else dp[i][0] = 0; } for (int i=0; i<len1; i++) { if (str1[i] == str2[0]) { dp[0][i] = 1; } else dp[0][i] = 0; } for (int i=1; i<len2; i++) { for (int j=1; j<len1; j++) { if (str2[i] == str1[j]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = 0; } if (dp[i][j] > max) { max = dp[i][j]; } } } return max; } int maxSubstrLength(const char* str) { if (str == NULL) { return 0; } int len = strlen(str); char* str1 = new char[len+1]; char* pstr1 = str1; while(len) { *pstr1++ = str[len-1]; len--; } return findMaxSubstr(str, str1); }
(1).
最长对称子串可能是偶数个字符,也可能是奇数个字符,分别进行判断。当判断的时候,以单个字符或者两个字符为中心,向左右两侧延伸,判断其左右两侧的字符是否相同,时间复杂度O(n^2).
int getMaxSubstring(char* pstr) { if(pstr==NULL) { return -1; } if(pstr==""||pstr[1]=='\0') { return 1; } int maxlen = 1; char* pchar = pstr + 1; while(*pchar != '\0') { //子串为奇数个字符 char *pleft = pchar - 1; char *pright = pchar + 1; while(pleft >= pstr && pright <= &pstr[strlen(pstr) - 1] && *pleft == *pright) { pleft--; pright++; } int templen = pright - pleft - 1; if(templen > maxlen) { maxlen = templen; } //子串为偶数个字符 pleft = pchar - 1; pright = pchar; while(pleft >= pstr && pright <= &pstr[strlen(pstr) - 1] && *pleft == *pright) { pleft--; pright++; } templen = pright - pleft - 1; if(templen > maxlen) { maxlen = templen; } pchar++; } return maxlen; }
(2).测试用例:
NULL
""
a
121
aabbaa
111222aabbaa
测试结果正确
(3).
编程时可能出现的bug有:
a. 没有对字符串为NULL的情况进行判断
b. 最长对称子串可能是偶数个字符也可能是奇数个字符,编程的时候可能考虑不全面
c. pleft >= pstr 和 pright <= &pstr[strlen(pstr) - 1] 没有添加等号,没有判断边界情况
(4).
上述算法的时间复杂度为O(n^2),也可以对字符串的每一个子串进行判断,遍历字符串的每一个字符,然后从该字符开始依次向后取以该字符开始的每一个子串,判断该子串是否为对称子串,然后取最长的对称子串即可,这种方法时间复杂度高,为O(n^3)。
#include <iostream> #include <cmath> #include <algorithm> #include <string.h> #include <stdio.h> #define maxn 110055 using namespace std; char ma[maxn * 2]; int mp[maxn * 2]; int l; int Manacher(char s[], int len) { int res = 0; l = 0; ma[l++] = '$'; ma[l++] = '#'; for(int i = 0; i < len; i++) { ma[l++] = s[i]; ma[l++] = '#'; } ma[l] = 0; int mx = 0, id = 0; for(int i = 0; i < l; i++) { mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1; while(ma[i + mp[i]] == ma[i - mp[i]]) { mp[i] ++; } if(i + mp[i] > mx) { mx = i + mp[i]; id = i; } } } char s[maxn]; int main() { scanf("%s", s); int len = strlen(s); Manacher(s, len); int ans = 0; for(int i = 0; i < l; i++) { ans = max(ans, mp[i]); } printf("%d\n", ans - 1); return 0; }
public static int longestSymmtricalLength(String str) { if (str == null || str.length() == 0) { return -1; } int symLen = 1; char[] letter = str.toCharArray(); int strLen = str.length(); int curIndex = 1; while (curIndex > 0 && curIndex < strLen - 1) { //奇数情况,两个数之间留一个,然后往两端扩展 int i = curIndex - 1; int j = curIndex + 1; while (i >= 0 && j <= (strLen - 1) && letter[i] == letter[j]) { i--;//如果两边的数相等,i左边的减一,往做扩展, j++;//如果两边的数相等,j往右边扩展,直到不符合条件, } int newLen = j - i - 1;//对称的新的长度 if (newLen > symLen) {//如果暂时的新的长度大于老的就替换掉老的, symLen = newLen; } i = curIndex;//偶数情况,,,紧挨着的两个数进行比较,其他情况和上面的奇数一样, j = curIndex + 1; while (i >= 0 && j <= (strLen - 1) && letter[i] == letter[j]) { i--; j++; } newLen = j - i - 1; if (newLen > symLen) { symLen = newLen; } curIndex++; } return symLen; }