logo标签列表

最长回文前缀

algorithmstring-algorithm
8
如何在O(n)时间复杂度内找到一个字符串的最长回文前缀？
5
这似乎是一道作业问题。如果是的话，应该打上相应的标签。 - Philip Starhill
1
定义最长回文前缀。时间复杂度应该为 O(n)，还是需要考虑内存使用？这是作业吗？ - Dirk Vollmar
2
我认为这个答案是一辆丰田汽车。 - Chris S
有一个左指针、右指针和LPal指针。如果S[Left] == S[Right]，则将左指针前进，右指针减少。否则，将左指针设置为0，减少右指针，将LPal设置为右指针。如果Left == Right，则返回。LPal将是最长回文前缀的最后一个索引。 - mk3009hppw
3个回答
9
使用滚动哈希。如果a是您的字符串，则让ha[x]成为从左到右计算出a中前x个字符的哈希值，让hr[x]成为从右到左计算出s中前x个字符的哈希值。您需要找到最后一个位置i，使得hf[i] = hb[i]。
C代码（使用每个方向的两个哈希来避免误报）：
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;
}
我认为代码示例中没有'从右到左'的部分... (i 从左到右，你只访问 a[i]). - Andre Holzner
@Andre Holzner - i 只从左到右移动。在每一步 i，您将在 match 中存储当前最长回文前缀的长度。只有滚动哈希会双向移动。 - IVlad
+1，我不知道它被称为“滚动哈希”。但是即使有两个哈希也不能保证每个正数都是“真实的”（更不用说使用如此不寻常的系数了 :))。这仅仅是因为对于某些长度_n_，存在比不同的整数对_(ha1, ha2)_更多的n字符字符串。如果您要验证每个正数，则在均匀字符串（'aaaaaaaa...'）上获得O(n^2)。 - Nikita Rybak
你可以在第一次遍历时将所有哈希值存储到数组中，然后从最长的候选项（整个字符串）开始，逐个字符减少。在这种情况下，如果您得到了验证的正面反馈，程序就完成了：您已经找到了最长的回文前缀。由于您的两个哈希具有足够罕见的误报率，因此对于合理的_n_值，程序仍然是“有点”O(n)。 - Nikita Rybak
Ivlad，我不明白ha1、ha2、hr1或hr2中的任何一个是如何从右到左计算的。在每次循环迭代中，只处理下一个元素（a[i]）的右侧。 - Andre Holzner
@Andre Holzner - 尝试逐步构建ha1和hr1。在i = 0时，我们有ha1 = a [0]和hr1 = a [0]。如果两者相等（显然它们会），我们就有了一个长度为1的回文前缀。在i = 1时，我们有ha1 = a [0] + base1 * a [1]和hr1 = a [1] + a [0] * base1。现在你看到这是怎么回事了吗？尝试为i = 2构建ha1和hr1。@Nikita Rybak - 是的，没有保证。 - IVlad
0

使用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];
    }
0
akalin.cx 上的 fastLongestPalindromes(..) 函数实际上是最坏情况下的 O(n) 复杂度吗？我看到了两个嵌套循环... - Andre Holzner
还没有读完所有内容，但是2个嵌套循环并不意味着二次复杂度。函数开头的continue应该确保内部循环只在少数情况下执行，并且每次执行该循环的总体复杂度为O(n)。 - Loïc Février
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接