最长回文子串

最长回文子串

在计算机科学中，最长的回文子串或最长的对称因子问题是找到给定字符串的最大长度连续子串的问题，该字符串也是回文。

例如，“香蕉”的最长回文子串是“anana”。 最长的回文子串不保证是唯一的; 例如，在字符串“abracadabra”中，没有长度大于3的回文子串，但是有两个长度为3的回文子串，即“aca”和“ada”。 在某些应用程序中，可能需要返回所有最大回文子串（即，所有子串本身是回文并且不能扩展到更大的回文子串），而不是仅返回一个子串或返回回文子串的最大长度。

Template

int Manacher(string s)
{
    string t = " #";///two chars
    int sz = s.size();
    for(int i = 0; i < sz; ++i)
    {
        t += s[i];
        t += "#";
    }

    sz = t.size();
    vector<int> vec(sz, 0);
    int mmax = 0, pos = 0, len = 0, center = 0;
    for(int i = 1; i < sz; ++i)///start from 1
    {
        vec[i] = mmax > i ? min(vec[2 * pos - i], mmax - i) : 1;
        while( t[ i + vec[i] ] == t[ i - vec[i] ] )
            ++vec[i];
        if (mmax < i + vec[i])
        {
            mmax = i + vec[i];
            pos = i;
        }
        if (len < vec[i])
        {
            len = vec[i];
            center = i;
        }
    }
    cout << s.substr( (center - len) / 2, len - 1) << '\n';
    return len - 1;
}

原文链接

HDU 3038 最长回文

题目链接

Code

#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int Manacher(string s)
{
    string t = " #";
    int sz = s.size();
    for(int i = 0; i < sz; ++i)
    {
        t += s[i];
        t += "#";
    }

    sz = t.size();
    vector<int> vec(sz, 0);
    int mmax = 0, pos = 0, len = 0, center = 0;
    for(int i = 1; i < sz; ++i)
    {
        vec[i] = mmax > i ? min(vec[2 * pos - i], mmax - i) : 1;
        while( t[ i + vec[i] ] == t[ i - vec[i] ] )
            ++vec[i];
        if (mmax < i + vec[i])
        {
            mmax = i + vec[i];
            pos = i;
        }
        if (len < vec[i])
        {
            len = vec[i];
            center = i;
        }
    }
//    cout << s.substr( (center - len) / 2, len - 1) << '\n';
    return len - 1;
}

int main()
{
    string s;
    int cnt = 1;
    while(cin >> s)
    {
        cout << Manacher(s) << '\n';
    }
    return 0;
}

POJ 3974 Palindrome

题目链接

#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int Manacher(string s)
{
    string t = " #";
    int sz = s.size();
    for(int i = 0; i < sz; ++i)
    {
        t += s[i];
        t += "#";
    }

    sz = t.size();
    vector<int> vec(sz, 0);
    int mmax = 0, pos = 0, len = 0, center = 0;
    for(int i = 1; i < sz; ++i)///从1开始
    {
        vec[i] = mmax > i ? min(vec[2 * pos - i], mmax - i) : 1;
        while( t[ i + vec[i] ] == t[ i - vec[i] ] )
            ++vec[i];
        if (mmax < i + vec[i])
        {
            mmax = i + vec[i];
            pos = i;
        }
        if (len < vec[i])
        {
            len = vec[i];
            center = i;
        }
    }
//    cout << s.substr( (center - len) / 2, len - 1) << '\n';
    return len - 1;
}

int main()
{
    string s;
    int cnt = 1;
    while(cin >> s)
    {
        if(s == "END")
            break;
        cout << "Case " << cnt++ << ": " ;
        cout << Manacher(s) << '\n';
    }
    return 0;
}