我的代码改了很久，还是不对。
所有报错都在第二行，也就是扩展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;
}
【以下回答由 GPT 生成】
【C++】扩展KMP算法的模版代码出错
问题分析：
根据你提供的代码，可以看出在扩展KMP算法的实现过程中有一些问题。代码实现的过程没有严格按照扩展KMP算法的步骤进行，导致程序的逻辑出现错误。具体问题如下：
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位置。
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;
}
}
// 其他代码...
}
请尝试使用修正后的代码再次进行测试，查看问题是否解决。
【相关推荐】