algorithm - 最長回文接頭辞

Question

O(n)で文字列の最長の回文プレフィックスを見つける方法は?

Answer 1

ローリング ハッシュを使用します。aが文字列の場合、左から右に計算された最初の文字のハッシュと、右から左に計算された最初の文字ha[x]のxハッシュとします。あなたは の最後の位置に興味があります。ahr[x]xsihf[i] = hb[i]

C のコード (誤検知を避けるために各方向に 2 つのハッシュを使用):

int match = n - 1;

int ha1 = 0, ha2 = 0, hr1 = 0, hr2 = 0;
int m1 = 1, m2 = 1;
for ( int i = 0; a[i]; ++i )
{
    ha1 = (ha1 + m1*a[i]) % mod1;
    ha2 = (ha2 + m2*a[i]) % mod2;

    hr1 = (a[i] + base1*hr1) % mod1;
    hr2 = (a[i] + base2*hr2) % mod2;

    m1 *= base1, m1 %= mod1;
    m2 *= base2, m2 %= mod2;

    if ( ha1 == hr1 && ha2 == hr2 )
        match = i;
}

Answer 2

O(n) での、プレフィックスではなくサブストリングに関する、より一般的な問題の解決策:

http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/

「最長回文接頭辞」の google での 2 番目の結果....

またはサフィックスツリーを使用したソリューション：

http://www.allisons.org/ll/AlgDS/Tree/Suffix/

Answer 3

Z アルゴリズムの使用 ( https://codeforces.com/blog/entry/3107 )。s が長さ m の与えられた文字列であると仮定します。コード：

    string rev="",str=s;
    int m=s.size(),longestPalindromicPrefix=1;
    if(m==0 || m==1)    longestPalindromicPrefix=m; 
    for(int i=m-1;i>=0;i--)
        rev+=s[i];
    s+='#';
    s+=rev;
    int n=s.size(),z[n+4],l=0,r=0;
    for(int i=1;i<n;i++){
        if(i>r){
            l=r=i;
            while(r<n && s[r-l]==s[r])
                r++;
            z[i]=r-l,r--;
        }
        else{
            int k=i-l;
            if(z[k]<r-i+1)
                z[i]=z[k];
            else{
                l=i;
                while(r<n && s[r-l]==s[r])
                    r++;
                z[i]=r-l,r--;
            }
        }
    }

    for(int i=m+1;i<n;i++){
        if(2*z[i]>=2*m-i && z[i]>longestPalindromicPrefix)
            longestPalindromicPrefix=z[i];
    }