1.POJ 3450 Coporate Identity
这两题的解法都是枚举子串，然后匹配，像这种题目以后可以不用KMP来做，直接字符串自带的strstr函数搞定，如果字符串未出现，该函数返回NULL。
下面贴出其比较。
代码：（KMP版）（1360ms 888KB）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[N][],tt[];
int next[]; void getnext(char *ss)
{
int m = strlen(ss);
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || ss[i] == ss[j])
next[++i] = ++j;
else
j = next[j];
}
} int kmp(char *ss,char *tt)
{
int n = strlen(ss);
int m = strlen(tt);
getnext(tt);
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || ss[i] == tt[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return ;
return ;
} int main()
{
int n,i,len,j,k,lengh;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(!kmp(ss[j],str))
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0')
cout<<"IDENTITY LOST\n";
else
cout<<ans<<endl;
}
return ;
}
代码：（strstr函数版）（454ms 912KB）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 4007 char ans[],str[];
char ss[N][],tt[];
int main()
{
int n,i,len,j,k,lengh;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(strstr(ss[j],str) == NULL)
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0')
cout<<"IDENTITY LOST\n";
else
cout<<ans<<endl;
}
return ;
}
2.POJ 3080 Blue Jeans
代码：（KMP版）（32ms 684KB）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[][],tt[];
int next[]; void getnext(char *ss)
{
int m = strlen(ss);
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || ss[i] == ss[j])
next[++i] = ++j;
else
j = next[j];
}
} int kmp(char *ss,char *tt)
{
int n = strlen(ss);
int m = strlen(tt);
getnext(tt);
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || ss[i] == tt[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return ;
return ;
} int main()
{
int n,i,len,j,k,lengh,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(!kmp(ss[j],str))
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0' || strlen(ans) < )
cout<<"no significant commonalities\n";
else
cout<<ans<<endl;
}
return ;
}
代码：（strstr函数版）（0ms 700KB）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[][]; int main()
{
int n,i,len,j,k,lengh,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(strstr(ss[j],str) == NULL)
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0' || strlen(ans) < )
cout<<"no significant commonalities\n";
else
cout<<ans<<endl;
}
return ;
}