【C++】扩展KMP算法的模版代码出错

Question

我的代码改了很久，还是不对。
所有报错都在第二行，也就是扩展KMP数组有问题，请帮忙找一下错误，谢谢！
原题链接：扩展KMP
代码如下：

#include <bits/stdc++.h>
using namespace std;
string s1,s2;
long long nxt[20000001],exkmp[20000001];
int main()
{
    cin>>s1>>s2;
    //nxt[i]:s2本身与以s2[i]开头的s2的后缀的LCP（最长公共前缀） 
    nxt[0]=s2.size();
    int k=1,p,l;
    for(int i=0;i+1<s2.size();i++)
    {
        if(s2[i]==s2[i+1])
            nxt[1]++;
        else break;
    }
    for(int i=2;i<s2.size();i++)
    {
        p=k+nxt[k]-1;
        l=nxt[i-k];
        if(l<=(p-i+1)-1)
        {
            nxt[i]=l;
        }
        else
        {
            int j;
            for(j=max(0,p-i+1);j+i<s2.size();j++)
            {
                if(s2[j]!=s2[j+i])
                    break;
            }
            nxt[i]=j;
            k=i;
        }
    }
    //exkmp:s2本身与以s1[i]开头的s1的后缀的LCP（最长公共前缀）
    k=1;
    for(int i=0;i<s2.size()&&i<s1.size();i++)
    {
        if(s2[i]==s1[i])
            exkmp[0]++;
        else
            break;
    }
    for(int i=1;i<s1.size();i++)
    {
        p=k+exkmp[k]-1;
        l=exkmp[i-k];
        if(l<=(p-i+1)-1)
        {
            exkmp[i]=l;
        }
        else
        {
            int j;
            for(j=max(0,p-i+1);j+i<s1.size()&&j<s2.size();j++)
            {
                if(s2[j]!=s1[j+i])
                    break;
            }
            exkmp[i]=j;
            k=i;
        }
    }
    //ans
    long long ans=0;
    for(int i=0;i<s2.size();i++)
        ans^=(i+1)*(nxt[i]+1);
    printf("%lld\n",ans);
        
    ans=0;
    for(int i=0;i<s1.size();i++)
        ans^=(i+1)*(exkmp[i]+1);
    printf("%lld",ans);
    return 0;
}

Answer 1

【以下回答由 GPT 生成】

【C++】扩展KMP算法的模版代码出错

问题分析：

根据你提供的代码，可以看出在扩展KMP算法的实现过程中有一些问题。代码实现的过程没有严格按照扩展KMP算法的步骤进行，导致程序的逻辑出现错误。具体问题如下：

1. nxt数组计算错误：在计算nxt数组时，代码中使用nxt[1]存储相邻字符相等的数量。然而，这个计算方式是错误的。根据扩展KMP算法的定义，nxt[i]表示s2本身与以s2[i]开头的s2的后缀的LCP（最长公共前缀）。正确的计算方式应该是从右往左遍历，比较s2[i]和s2[i+1]之间的关系，当二者相等时，nxt[i] = nxt[i+1] + 1，并且将k指针重新定位到i位置。

2. exkmp数组计算错误：在计算exkmp数组时，代码中使用exkmp[0]存储相邻字符相等的数量。然而，这个计算方式也是错误的。根据扩展KMP算法的定义，exkmp[i]表示s2本身与以s1[i]开头的s1的后缀的LCP（最长公共前缀）。正确的计算方式应该是从右往左遍历，比较s2[j]和s1[i+j]之间的关系，当二者相等时，exkmp[i] = exkmp[i+1] + 1，并且将k指针重新定位到i位置。

解决方案：

基于以上分析，以下是修正后的代码：

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
long long nxt[20000001], exkmp[20000001];

int main()
{
    cin >> s1 >> s2;
    // nxt[i]: s2本身与以s2[i]开头的s2的后缀的LCP（最长公共前缀）
    nxt[s2.size() - 1] = s2.size();
    int k = s2.size() - 1, p, l;
    for (int i = s2.size() - 1; i > 0; i--)
    {
        if (s2[i] == s2[i - 1])
            nxt[i - 1] = nxt[i] - 1;
        else
            break;
    }
    for (int i = s2.size() - 2; i >= 0; i--)
    {
        p = k - nxt[k] + 1;
        l = nxt[i - k];
        if (l <= (i - p))
        {
            nxt[i] = l;
        }
        else
        {
            int j;
            for (j = max(0, p); j + i < s2.size(); j++)
            {
                if (s2[j] != s2[j + i])
                    break;
            }
            nxt[i] = j;
            k = i;
        }
    }
    // exkmp: s2本身与以s1[i]开头的s1的后缀的LCP（最长公共前缀）
    k = s2.size() - 1;
    for (int i = 0; i < s2.size() && i < s1.size(); i++)
    {
        if (s2[i] == s1[i])
            exkmp[0]++;
        else
            break;
    }
    for (int i = 1; i < s1.size(); i++)
    {
        p = k - exkmp[k] + 1;
        l = exkmp[i - k];
        if (l <= (i - p))
        {
            exkmp[i] = l;
        }
        else
        {
            int j;
            for (j = max(0, p); j < s2.size(); j++)
            {
                if (s2[j] != s1[j + i])
                    break;
            }
            exkmp[i] = j;
            k = i;
        }
    }
    // 其他代码...
}

请尝试使用修正后的代码再次进行测试，查看问题是否解决。

【相关推荐】

• 你看下这篇博客吧, 应该有用👉 ：【算法】C++中的正则表达式（一定程度上可代替KMP等）
• 您还可以看一下 李飞老师的C语言开发之数据结构与算法三课程中的 KMP算法(代码实现)小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 【数据结构】第四章 串（2）朴素模式匹配算法、KMP算法（C++）中的 总结： 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^