HDU 2594 扩展kmp模板题

　题目大意：

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <climits>

 #include <cmath>

 #include <cstdlib>

 using namespace std;

 #define ll long long

 #define N 1000100

 char a[N] , b[N];

 int _next[N] , extend[N] , len1 , len2;

 void get_next(char *T){// _next[i]: 以第i位置开始的子串 与 T的公共前缀

      int i,length = strlen(T);

      _next[] = length;

      for(i = ;i<length- && T[i]==T[i+]; i++);

           _next[] = i;

           int a = ;

           for(int k = ; k < length; k++){

                   int p = a+_next[a]-, L = _next[k-a];

                   if( (k-)+L >= p ){

                        int j = (p-k+)>? (p-k+) : ;

                        while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较

                        _next[k] = j, a = k;

                   }

                   else _next[k] = L;

          }

 }

 void getextend(char *S,char *T){

     int maxl=max(len1 , len2);

     for(int i= ; i<=maxl ; i++) _next[i]=;

     get_next(T);

     int Slen = strlen(S), Tlen = strlen(T), a = ;

     int MinLen = Slen>Tlen?Tlen:Slen;

     while(a<MinLen && S[a]==T[a]) a++;

     extend[] = a, a = ;

     for(int k = ; k < Slen; k++){

       int p = a+extend[a]-, L = _next[k-a];

       if( (k-)+L >= p ){

            int j = (p-k+)>? (p-k+) : ;

            while(k+j<Slen && j<Tlen && S[k+j]==T[j] ) j++;

            extend[k] = j;a = k;

       }

       else extend[k] = L;

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("a.in" , "r" , stdin);

     #endif

     while(~scanf("%s%s" , a , b))

     {

         getextend(b , a);

         len1 = strlen(a) , len2 = strlen(b);

         int ret = ;

         for(int i= ; i<len2 ; i++)

             if(extend[i]>ret&&extend[i]+i==len2) ret = extend[i];

         if(!ret) puts("");

         else{

             strncpy(a , b+(len2-ret) , ret);

             a[ret] = '\0';

             printf("%s %d\n" , a, ret);

         }

     }

     return ;

 }