扩展KMP总结（模板题hdu2594）

模板题：hdu2594 （扩展KMP）

http://acm.hdu.edu.cn/showproblem.php?pid=2594

题目大意：给定两个字符串，在第一个字符串中找到一个最大前缀作为第二个字符串的后缀

思路：将S1作为模式串然后在s2中寻找，求出s1的next数组，nxt[i]:x[i...m-1]与x[0...m-1]的最长公共前缀。同时求出s2的extend数组，extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀

借鉴kuangbin的模板：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
/*
* 扩展KMP算法
*/
//nxt[i]:x[i...m-1]与x[0...m-1]的最长公共前缀
//extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
int nxt[100050];
int extend[100050];
char s[100050], t[100050];
void pre_EKMP(char x[],int m,int nxt[])
{
 nxt[0]=m;
 int j=0;
 while(j+1<m && x[j]==x[j+1]) j++;
 nxt[1]=j;
 int k=1;
 for(int i=2;i<m;i++)
 {
  int p=nxt[k]+k-1;
  int L=nxt[i-k];
  if(i+L<p+1)nxt[i]=L;
  else
  {
   j=max(0,p-i+1);
   while(i+j<m && x[i+j]==x[j])j++;
   nxt[i]=j;
   k=i;
  }
 }
}
void EKMP(char x[],int m,char y[],int n,int nxt[],int extend[])
{
 pre_EKMP(x,m,nxt);
 int j=0;
 while(j<n && j<m && x[j]==y[j]) j++;
 extend[0]=j;
 int k=0;
 for(int i=1;i<n;i++)
 {
  int p=extend[k]+k-1;
  int L=nxt[i-k];
  if(i+L<p+1)
   extend[i]=L;
  else
  {
   j=max(0,p-i+1);
   while(i+j<n && j<m && y[i+j]==x[j]) j++;
   extend[i]=j;
   k=i;
  }
 }
}

int main()
{
    while(cin >> s >> t)
    {
     int slen = strlen(s),tlen = strlen(t);
        EKMP(s,slen,t,tlen,nxt,extend);
        int ans = 0;

        for(int i = tlen - 1, j = 0; j < slen; j++, i--)
        {
            if(extend[i] == tlen - i)
            {
                ans = max(ans, extend[i]);
            }
        }
        if(ans)
        {
            for(int i = 0; i < ans; i++)
                cout << s[i];
            cout << " ";
        }
        cout << ans <<endl;
    }
    return 0;
}