POJ 3450 Corporate Identity KMP

题意：找所有字符串中的最长公共字串
解题思路：KMP+剪枝，因为如果我们知道前缀如果不满足条件，所有以这个开头的都不行。
解题代码：
  1 // File Name: getnext.cpp
  2 // Author: darkdream
  3 // Created Time: 2014年09月09日 星期二 22时35分02秒
  4 
  5 #include<vector>
  6 #include<list>
  7 #include<map>
  8 #include<set>
  9 #include<deque>
 10 #include<stack>
 11 #include<bitset>
 12 #include<algorithm>
 13 #include<functional>
 14 #include<numeric>
 15 #include<utility>
 16 #include<sstream>
 17 #include<iostream>
 18 #include<iomanip>
 19 #include<cstdio>
 20 #include<cmath>
 21 #include<cstdlib>
 22 #include<cstring>
 23 #include<ctime>
 24 #define LL long long
 25 
 26 using namespace std;
 27 char str1[300];
 28 char str[4004][300];
 29 int next[305];
 30 void split(int x ,int y )
 31 {
 32    int t = -1;
 33    for(int i = x ;i <= y ;i ++)
 34    {
 35       str1[++t] =  str[1][i];
 36    }
 37    str1[++t] = '';
 38 }
 39 void getnext()
 40 {
 41     int len = strlen(str1);
 42     next[0] = -1; 
 43     int k = -1;
 44     int j = 0 ; 
 45     while(j <= len - 1)
 46     {
 47         if(k == -1 || str1[j] == str1[k])
 48         {
 49             ++j; 
 50             ++k;
 51             next[j] = k ;
 52         }
 53         else {
 54             k = next[k];
 55         }
 56     }
 57 }
 58 int  kmp(int k)
 59 {
 60     int j = 0 ; 
 61     int i = 0 ;
 62     int len = strlen(str1);
 63 
 64     while(j < strlen(str[k]))
 65     {
 66        if(i == -1 || str1[i] == str[k][j])
 67        {
 68          i ++ ; 
 69          j ++ ; 
 70        }else{
 71          i = next[i];
 72        }
 73        if(i == len)
 74        {
 75           return 1; 
 76        }
 77     }
 78     return 0 ;
 79 }
 80 int n ;
 81 char ans[100];
 82 int maxlen; 
 83 int  solve(int x, int y)
 84 {
 85     split(x,y);
 86 //    puts(str1);
 87     getnext();
 88     for(int i = 2 ;i <= n;i ++)
 89     {
 90       if(!kmp(i))
 91       {
 92          return 0 ;  
 93       }
 94     }
 95     //puts(str1);
 96     if(y - x + 1 > maxlen)
 97     {
 98          strcpy(ans,str1);
 99          maxlen = y-x +1; 
100     }
101     else if(y -x +1 == maxlen)
102     {
103        if(strcmp(ans,str1) > 0)
104            strcpy(ans,str1);
105     }
106     return 1;
107 }
108 int main(){
109     while(scanf("%d",&n),n)
110     {
111       maxlen = 0 ; 
112       int minlen = 1e9;
113       for(int i = 1 ;i <= n;i ++)
114       {
115         scanf("%s",str[i]);
116         if(strlen(str[i]) < minlen)
117         {
118           minlen = strlen(str[i]);
119         }
120       }
121       for(int i = 0 ;i < strlen(str[1]) ;i ++)
122         for(int j = i;j < strlen(str[1]) ;j ++)
123         {
124           if(!solve(i,j) || j-i+1 > minlen)
125           {
126              break;
127           }
128         }
129      if(maxlen > 0)
130       {
131         puts(ans);
132       }else {
133         printf("IDENTITY LOST
");
134       }
135     }
136     return 0;
137 }
View Code
没有梦想，何谈远方