扩展kmp模板

const int maxn = 5 * 1e4 + 100;

char s1[maxn], s2[maxn];

int ne[maxn], ex[maxn];

void Getnext(char *st)          //得到next数组，是把st既当成母串又当成子串
{
 int len = strlen(st);
 ne[0] = len;
 int i = 0;
 while(i + 1 < len && st[i] == st[i + 1])
  i ++;
 ne[1] = i;
 int po = 1;
 for(i = 2; i < len; ++ i)
 {
  if(ne[i - po] + i < ne[po] + po)
   ne[i] = ne[i - po];
  else 
  {
   int j;
   j = ne[po] + po - i;
   if(j < 0)
    j = 0;
   while(i + j < len && j < len && st[i + j] == st[j])
    j ++;
   ne[i] = j;
   po = i;
  }
 }
}

void Exkmp(char *s2, char *s1)       //s1是母串，s2是子串
{
 Getnext(s2);            //得到next数组
 int len1 = strlen(s1), len2 = strlen(s2);
 int i, j;
 i = 0;
 while(i < len1 && i < len2 && s1[i] == s2[i])
  i++;
 ex[0] = i;
 int po = 0;
 for(i = 1; i < len1; ++ i)
 {
  if(ne[i - po] + i < ex[po] + po)   //第一种情况直接得出结果
   ex[i] = ne[i - po];
  else                              
  {
   j = ex[po] + po - i;           //第二种情况需要继续往后匹配
   if(j < 0)
    j = 0;
   while(j < len2 && i + j < len1 && s1[i + j] == s2[j])
    j++;
   ex[i] = j;
   po = i;
  }
 }
}