EXKMP模板小结

胡乱分析

什么是EXKMP?

kmp就是当前这一部分的前缀与后缀的一个最大等值，然后等着线性匹配的时候如果出现了失配那么能够快速匹配到位的一种算法那么既然是EXKMP那么肯定是要有EX的部分的，那一部分就是EXKMP是子串与所有的主串所匹配的最大前缀长度
例子
aabbabaaab
aabb
4 1 0 0 1 0 2 3 1 0
aabb跟主串第一个位置是有最大的4个前缀长度，第二个位置只有一个a最大其他的同理

EXKMP怎么实现?

首先我们需要两个数组也就是子串的next数组这里的next数组和kmp的不一样是上面说的全部的匹配然后一个主串的ex数组存的就是答案具体的证明可以看这位大佬的博文

模板需要注意的事项

实际上具体的实现的步骤就是复读两遍一个同样的算法首先计算子串的的next数组，先暴力出第二个第一个就是lenb然后从第三个开始计算k代表当前所运行的位置p代表最大的匹配的范围l是一个计算的变量
其中p=k+next[k]-1 l=next[i-k+1]
判断一下如果i+l<p+1
那么直接next[i]=l
否则进行下一波的匹配
令j=p-i+1
然后接着匹配b[j]与b[i+j]看是否能相等最后把next[i]=j即可更新一下k匹配的时候同理不同的地方就是l=next[i-k+1]不是l=ex[i-k+1]

代码

#include <bits/stdc++.h>
using namespace std;
char a[10005],b[10005];
int la,lb,nex[10005],ex[10005];
void exkmp()
{
  nex[1]=lb;
  int x=1;
  while(b[x]==b[x+1]&&x+1<=lb)
  x++;
  nex[2]=x-1;
  int k=2;
  for(int i=3;i<=lb;i++)
  {
    int p=k+nex[k]-1;
    int l=nex[i-k+1];
    if(i+l<p+1)
    nex[i]=l;
    else
    {
      int j=p-i+1;
      if(j<0)
      j=0;
      while(b[j+1]==b[i+j]&&i+j<=lb)
      j++;
      nex[i]=j;
      k=i;
    }
  }
  x=1;
  while(a[x]==b[x]&&x<=lb)
  x++;
  ex[1]=x-1;
  k=1;
  for(int i=2;i<=la;i++)
  {
    int p=k+ex[k]-1;
    int l=nex[i-k+1];
    if(i+l<p+1)
    ex[i]=l;
    else
    {
      int j=p-i+1;
      if(j<0)
      j=0;
      while(b[j+1]==a[i+j]&&i+j<=la&&j<=lb)
      j++;
      ex[i]=j;
      k=i;
    }
  }
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>a+1>>b+1;
  la=strlen(a+1);
  lb=strlen(b+1);
  exkmp();
  for(int i=1;i<=la;i++)
  cout<<ex[i]<<" ";
}