我正在解决一个问题,要在长度为20,000个字符的字符串中找到最大回文串。我曾尝试检查每个子字符串是否是回文串,虽然可行,但速度显然太慢了。经过一番搜索,我发现了这个不错的算法:http://stevekrenzel.com/articles/longest-palnidrome。我尝试实现它,但是无法让它正常工作。此外,给定的字符串包含非法字符,因此我必须将其转换为仅含合法字符,并输出所有字符的最长回文串。
以下是我的尝试:
以下是我的尝试:
int len = original.length();
int longest = 0;
string answer;
for (int i = 0; i < len-1; i++){
int lower(0), upper(0);
if (len % 2 == 0){
lower = i;
upper = i+1;
} else {
lower = i;
upper = i;
}
while (lower >= 0 && upper <= len){
string s2 = original.substr(lower,upper-lower+1);
string s = convert(s2);
if (s[0] == s[s.length()-1]){
lower -= 1;
upper += 1;
} else {
if (s.length() > longest){
longest = s.length();
answer = s2;
}
break;
}
}
}
我无法让它工作,我已经在纸上尝试使用了这个确切的算法,并且它可行,请帮忙。如果需要,这是完整的代码:http://pastebin.com/sSskr3GY
编辑:
int longest = 0;
string answer;
string converted = convert(original);
int len = converted.length();
if (len % 2 == 0){
for (int i = 0; i < len - 1; i++){
int lower(i),upper(i+1);
while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){
lower -= 1;
upper += 1;
}
string s = converted.substr(lower+1,upper-lower-1);
if (s.length() > longest){
longest = s.length();
answer = s;
}
}
} else {
for (int i = 0; i < len; i++){
int lower(i), upper(i);
while (lower >= 0 && upper <= len && converted[lower] == converted[upper]){
lower -= 1;
upper += 1;
}
string s = converted.substr(lower+1,upper-lower-1);
if (s.length() > longest){
longest = s.length();
answer = s;
}
}
}
好的,我解决了问题,它完美地工作了,但仅当转换后的字符串长度为奇数时才有效。请帮忙。