之前写KMP模板的时候，nx[i]代表最大的一个x，使s[1,x-1]是s[1,i-1]的后缀。（方法1）
然而网上还有另一种方法求nx数组，nx[i]表示最大的一个x，使s[1,x]是s[1,i]的后缀。（方法2）
两种nx数组在具体匹配的时候方法稍有不同，但都能正确匹配字符串。
但是在做字符串DP题的时候，发现网上的题解大多是利用第二种nx数组的性质进行状态的转移。
当时试着写了一下那种nx的求法，但是觉得很别扭，用不惯也记不住。
不知所措。
今天看了一下洛谷的KMP模板（P3375）（传送门），发现得求出第二种nx数组……
这回把第二种求法忘了，也很反感那么写。
于是立志要找出两种方法的联系。
很简单嘛：nx2[i]=nx1[i+1]-1
同时，getnx的时候要走到m+1（m为模式串长），这样nx[m+1]才有值。
给一个洛谷P3375的代码。
注意getnx的改动和最后要求输出nx数组的时候是怎么操作的。
#include<cstdio>
#include<cstring> char s1[],s2[];
int nx[];
int pos[],cnt;
int n,m; void getnx()
{
nx[]=;
for(int i=,j=;i<=m+;)
{
nx[i]=j;
while(j&&s2[i]!=s2[j])j=nx[j];
i++,j++;
}
} void kmp()
{
for(int i=,j=;i<=n;)
{
while(j&&s1[i]!=s2[j])j=nx[j];
if(j==m)
{
pos[++cnt]=i-m+;
j=nx[j];
}
else i++,j++;
}
} int main()
{
scanf("%s",s1+);
scanf("%s",s2+);
n=strlen(s1+);
m=strlen(s2+);
getnx();
kmp();
for(int i=;i<=cnt;i++)printf("%d\n",pos[i]);
for(int i=;i<=m;i++)printf("%d ",nx[i+]-);
return ;
}
