hdu1238Substrings

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

找多个串的最长公共子串。

枚举最短串的子串temp，求子串的反串vs，用其他串与vs或temp匹配（一个成功即可），其他串都存在该子串则更新答案。

用KMP 31ms，用strstr 0ms。

KMP：

 1 #include<cstdio>
 2 #include<cstring>
 3 const int maxn=110;
 4 const int maxm=110;
 5 char s[maxn][maxm];
 6 char temp[maxm],vs[maxm];
 7 int n;
 8 int nex1[maxm],nex2[maxm];
 9 
10 void getnex(char* p,int *nex)
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 
23 bool fd(char*t,char *p,int *nex)
24 {
25     int tl=strlen(t);
26     int pl=strlen(p);
27     int i=0,j=0;
28     while(i<tl&&j<pl)
29     {
30         while(j>0&&t[i]!=p[j])
31             j=nex[j];
32         if(t[i]==p[j])
33         {
34             j++;
35             i++;
36         }
37         else i++;
38         if(j==pl) return true;
39     }
40     return false;
41 }
42 
43 int main()
44 {
45 int t;
46 scanf("%d",&t);
47     while(t--)
48     {
49         scanf("%d",&n);
50         int id=0,len=110,tlen;
51         for(int i=0;i<n;i++)
52         {
53 
54             scanf("%s",s[i]);
55             tlen=strlen(s[i]);
56             if(len>tlen) {id=i;len=tlen;}
57         }
58         int m=0;
59         //枚举子串！！！
60         for(int i=0;i<len;i++)
61             for(int h=i;h<len;h++)
62         {
63             int is=0,vis=1;
64             for(int j=i;j<=h;j++)
65             {
66                 temp[is++]=s[id][j];
67             }
68             temp[is]='';
69              int y=0;
70             for(int h=is-1;h>=0;h--)  //temp翻转得到vs
71                 vs[y++]=temp[h];
72                 vs[is]='';
73             getnex(temp,nex1);
74             getnex(vs,nex2);
75             for(int k=0;k<n;k++){
76                 if(k==id) continue;
77                 if(!fd(s[k],temp,nex1)&&!fd(s[k],vs,nex2))
78                     {
79                         vis=0;
80                         break;
81                     }
82 
83             }
84             if(vis&&m<is) m=is;
85 
86         }
87          printf("%d
",m);
88 
89     }
90 }

strstr：

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