在字符串实现中找到最大的回文

Question

我正在尝试解决一个问题,要求在一个字符串中找到最多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;
        }
    }
}

好的,所以我解决了问题,它完全正常,但只有当转换后的字符串的长度是奇数时.请帮忙.

Answer 1

我可以看到两个主要错误：

1. 将上/下指针初始化为 i,i 还是 i,i+1 取决于要查找的回文长度的奇偶性，而不是原始字符串。因此（无需任何进一步优化）您将需要两个单独的循环，其中 i 从 0 到 len (len-1)，一个用于奇数回文长度，另一个用于偶数。
2. 算法应仅对转换后的字符串执行。您必须先转换原始字符串才能使其工作。

考虑这个字符串：（abc^ba其中^是非法字符），排除非法字符的最长回文显然是abcba，但是当你到达i==2，并将下限/上限移出 1 时，它们将定义子bc^字符串，转换后它变成bc，并且b != c所以你承认这个回文不能扩展。