扩展kmp代码模板

next[ i ] 表示以i开始的后缀字串和原字串的最长前缀长度，即S[ i , i + next[i] ) = S[ 0 , next[i] )为左闭右开区间。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 2;
void getNext(int *next, char *s,int sl);
void exKmp(int *ex, char *t, char *s,int tl,int sl);
int ex[MAXN], tl, sl, mnext[MAXN];

char t[MAXN], s[MAXN];


void getNext()
{
 int i = 0, j, po=1;
 mnext[0] = sl;
 while (s[i] == s[i + 1])i++;
 mnext[1] = i;
 for (int i = 2; i < sl; i++)
 {
  if (po + mnext[po] > i + mnext[i - po])mnext[i] = mnext[i - po];
  else
  {
   int j = po + mnext[po] - i;
   if (j < 0)j = 0;
   while (j + i < sl&&s[i + j] == s[j])j++;
   mnext[i] = j;
   po = i;//不要忘记更新po位置
  }
 }
}

void exKmp()
{
 int i = 0;
 while (t[i] == s[i] && i < sl&&i < tl)i++;
 ex[0] = i;
 int po = 0;
 for (int i = 1; i < tl; i++)
 {
  if (po + ex[po] > i + mnext[i - po])ex[i] = mnext[i - po];
  else
  {
   int j = po + ex[po] - i;
   if (j < 0)j = 0;
   while (i + j < tl&&j < sl&&t[i + j] == s[j])j++;
   ex[i] = j;
   po = i;//不要忘记更新po位置
  }
 }
}