CF #93 div1 B. Password KMP/Z

题目链接：http://codeforces.com/problemset/problem/126/B

大意：给一个字符串，问最长的既是前缀又是后缀又是中缀（这里指在内部出现）的子串。

我自己的做法是用KMP的next数组，对所有既是前缀又是中缀的位置计数，再从next[n]开始走next，也即枚举所有既是前缀又是后缀的子串，看cnt[i]是否大于0，如果大于0则说明作为中缀出现过（也即有大于i的某个位置的next为i）

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 using namespace std;

 const int N=1e6+;

 char s[N];

 int next[N];

 int cnt[N];

 void getNext(char *word,int n=){

     n=(n==)?strlen(word):n;

     memset(next,,sizeof(next));

     int i,j;

     for (i=;i<n;i++){

         j=i;

         while (j){

             j=next[j];

             if (word[i]==word[j]){

                 next[i+]=j+;

                 break;

             }

         }

     }

 }

 int main () {

     scanf("%s",s);

     int n=strlen(s);

     getNext(s,n);

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

         cnt[next[i]]++;

     if (next[n]==)

         puts("Just a legend");

     else {

         for (int i=next[n];i;i=next[i]) {

             if (cnt[i]) {

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

                     printf("%c",s[j]);

                 puts("");

                 return ;

             }

         }

         puts("Just a legend");

     }

     return ;

 }

还有一种枚举方法是扫描所有可能的中缀末位，取next[i]的最大值，也即求出最大的既是前缀又是中缀的子串，再从next[n]开始走next，第一次走到0<next[i]<=len时，也即找到了子串。

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 using namespace std;

 const int N=1e6+;

 char s[N];

 int next[N];

 void getNext(char *word,int n=){

     n=(n==)?strlen(word):n;

     memset(next,,sizeof(next));

     int i,j;

     for (i=;i<n;i++){

         j=i;

         while (j){

             j=next[j];

             if (word[i]==word[j]){

                 next[i+]=j+;

                 break;

             }

         }

     }

 }

 int main () {

     scanf("%s",s);

     int n=strlen(s);

     getNext(s,n);

     int len=;

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

         len=max(len,next[i]);

     for (int i=next[n];i>;i=next[i]) {

         if (i>len) continue;

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

             printf("%c",s[j]);

         puts("");

         return ;

     }

     puts("Just a legend");

     return ;

 }

第三种方法是用z算法，也就是算出每个位置与本串的最长公共前缀。再枚举所有后缀，check当前后缀是否也是前缀，如果是的话，则看之前是否有z[i]也就是与本串的LCP大于当前后缀长度，如果有，则当前后缀也一定可以作为中缀出现，当前后缀是最长的符合题意的子串。

 #include <iostream>

 #include <vector>

 #include <algorithm>

 #include <string>

 #include <string.h>

 #include <stdio.h>

 #include <math.h>

 #include <stdlib.h>

 #include <queue>

 #include <stack>

 #include <map>

 #include <set>

 using namespace std;

 const int N=1e6+;

 char s[N];

 int z[N];

 void Z_match(char *s,int n=) {

     n=(n==)?strlen(s):n;

     z[]=n;

     int l=,r=;

     for (int i=;i<n;i++) {

         if (i>r) {

             l=i,r=i;

             while (r<n&&s[r-i]==s[r]) r++;

             z[i]=r-l;

             r--;

         }

         else {

             int k=i-l;

             if (z[k]<r-i+)

                 z[i]=z[k];

             else {

                 l=i;

                 while (r<n&&s[r-i]==s[r]) r++;

                 z[i]=r-l;

                 r--;

             }

         }

     }

 }

 int main () {

     scanf("%s",s);

     int n=strlen(s);

     Z_match(s,n);

     int ret=,maxZ=;

     for (int i=;i<n;i++) {

         if (z[i]==n-i) {

             if (maxZ>=n-i) {

                 ret=n-i;

                 break;

             }

         }

         maxZ=max(maxZ,z[i]);

     }

     if (ret==)

         puts("Just a legend");

     else {

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

             printf("%c",s[i]);

         puts("");

     }

     return ;

 }

CF #93 div1 B. Password KMP/Z的相关教程结束。