hdu2328Corporate Identity

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2328

多串找最长公共字串。

KMP：951ms

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=4010;
 4 const int maxm=210;
 5 char s[maxn][maxm];
 6 char ans[maxm],temp[maxm];
 7 int n;
 8 
 9 int nex[maxm];
10 void getnex(char* p)
11 {
12     int pl=strlen(p);
13     int i=0,j=-1;
14     nex[0]=-1;
15     while(i<pl)
16     {
17         if(j==-1||p[i]==p[j])
18             nex[++i]=++j;
19         else j=nex[j];
20     }
21 }
22 bool fd(char*t,char *p)
23 {
24     int tl=strlen(t);
25     int pl=strlen(p);
26     int i=0,j=0;
27     while(i<tl&&j<pl)
28     {
29         while(j>0&&t[i]!=p[j])
30             j=nex[j];
31         if(t[i]==p[j])
32         {
33             j++;
34             i++;
35         }
36         else i++;
37         if(j==pl) return true;
38     }
39     return false;
40 }
41 
42 int main()
43 {
44 
45     while(scanf("%d",&n)&&n)
46     {
47         int id=0,len=210,tlen;
48         for(int i=0;i<n;i++)
49         {
50 
51             scanf("%s",s[i]);
52             tlen=strlen(s[i]);
53             if(len>tlen) {id=i;len=tlen;}
54         }
55         int m=0;
56         //枚举子串！！！
57         for(int i=0;i<len;i++)
58             for(int h=i;h<len;h++)
59         {
60             int is=0,vis=1;
61             for(int j=i;j<=h;j++)
62             {
63                 temp[is++]=s[id][j];
64             }
65             temp[is]='';
66             getnex(temp);
67             for(int k=0;k<n;k++)
68                 if(k==id) continue;
69                 else {
70                 if(!fd(s[k],temp))
71                     {
72                         vis=0;
73                         break;
74                     }
75                 }
76             if(vis&&m<is) {m=is;memcpy(ans,temp,sizeof(temp));}
77             else if(vis&&m==is&&strcmp(ans,temp)>0) memcpy(ans,temp,sizeof(temp));
78 
79         }
80         if(m) printf("%s
",ans);
81         else printf("IDENTITY LOST
");
82     }
83 }

strstr：124ms

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=4010;
 4 const int maxm=210;
 5 char s[maxn][maxm];
 6 char ans[maxm],temp[maxm];
 7 int n;
 8 
 9 int main()
10 {
11 
12     while(scanf("%d",&n)&&n)
13     {
14         int id=0,len=210,tlen;
15         for(int i=0;i<n;i++)
16         {
17 
18             scanf("%s",s[i]);
19             tlen=strlen(s[i]);
20             if(len>tlen) {id=i;len=tlen;}
21         }
22         int m=0;
23         //枚举子串！！！
24         for(int i=0;i<len;i++)
25             for(int h=i;h<len;h++)
26         {
27             int is=0,vis=1;
28             for(int j=i;j<=h;j++)
29             {
30                 temp[is++]=s[id][j];
31             }
32             temp[is]='';
33             for(int k=0;k<n;k++)
34                 if(k==id) continue;
35                 else {
36                    if(!strstr(s[k],temp))
37                     {
38                         vis=0;
39                         break;
40                     }
41                 }
42             if(vis&&m<is) {m=is;memcpy(ans,temp,sizeof(temp));}
43             else if(vis&&m==is&&strcmp(ans,temp)>0) memcpy(ans,temp,sizeof(temp));
44 
45         }
46         if(m) printf("%s
",ans);
47         else printf("IDENTITY LOST
");
48     }
49 }

函数名: strstr 原型是朴素的字符串比较方法
功能: 在字符串中查找指定字符串的第一次出现
用法: char *strstr(char *str1, char *str2);
用法：#include <string.h>
功能：
str1: 被查找目标
str2:要查找对象
该函数返回str2第一次在str1中的位置的指针，如果没有找到，返回NULL