【HDOJ5510】Bazinga（KMP）

题意：给定n个由小写字母组成的字符串，第i个字符串为a[i]，求最大的j满足存在1<=i<j，a[i]不是a[j]的子串，无解输出-1

T<=50,n<=500,len[i]<=2000

思路：队友写的，抱大腿

判断某个串是否是另一个串的子串可以使用KMP

有一个优化：若a[i-1]是a[i]的子串，则将a[i-1]标记，后面不需要再枚举它

队友的写法是把连续一段缩成了一个

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long 
 4 const int maxn=505;
 5 char s[maxn][maxn<<2]; 
 6 int nxt[maxn][maxn<<2];
 7 int len[maxn];
 8 int p[maxn];
 9 void getnext(int x)
10 {
11     int i=0; int j=1;
12     nxt[x][1]=0;
13     int n=len[x];
14     while(j<=n)
15     {
16         if(!i||s[x][i]==s[x][j]) 
17         {
18             i++; j++;
19             nxt[x][j]=i;
20         }
21          else i=nxt[x][i];
22     }
23 }
24 int kmp(int x,int y)
25 {
26     int i=1; int j=1;
27     int m=len[x];
28     int n=len[y];
29     while(j<=m)
30     {
31         if(!i||s[y][i]==s[x][j])
32         {
33             i++; j++;
34             if(i>n)
35             {
36                 return 1;
37             }
38         }
39          else i=nxt[y][i];
40     }
41     return 0;
42 }
43 int main()
44 {
45     int T;
46     scanf("%d",&T);
47     int cas=0;
48     while(T--)
49     {
50         int n;
51         scanf("%d",&n);
52         memset(s,0,sizeof(s));
53         for(int i=1;i<=n;i++)
54         {
55             scanf("%s",s[i]+1);
56             len[i]=strlen(s[i]+1);
57             getnext(i);
58         }
59         int g=0;
60         int num=0;
61         int r=n;
62         int l=0;;
63         for(int i=n;i>=2;i--)
64         {
65             if(!kmp(i,i-1))
66             {
67                 if(num==0)
68                 {
69                     l=i;
70                 }
71                 p[++num]=i-1;
72             }
73         }
74         printf("Case #%d: ",++cas);
75         if(!l)
76             printf("-1
");
77         else
78         {
79             for(int i=1;i<=num;i++)
80             {
81                 for(int j=r;j>=l;j--)
82                 {
83                     if(!kmp(j,p[i]))
84                     {
85                         l=j;
86                         break;
87                     }
88                 }
89                 if(l==r)
90                     break;
91             }
92             printf("%d
",l);
93         }
94     }
95 }