题意:
给(n(1 leq n leq 500))个字符串,求一个最大的(i),使得存在一个(S_{j})不是(S_i)的子串。
分析:
维护两个指针(l,r)
那么有两种情况:
- 如果(S_l)是(S_r)的子串,那么(l)++。
- 如果(S_l)不是是(S_r)的子串,那么将答案更新为(r),然后(r)++。
考虑(S_{r+1})的时候为什么同样不考虑(S_l)之前的串了呢?
因为(S_l)之前的串都是后面某个串的子串,所以如果他们中有不是(S_{r+1})子串的串的话,那么一定有对应的那个串也不是(S_{r+1})的子串。这样保证(r)一定能更新到(ans)。
因此降了一维的复杂度。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500 + 5;
const int maxl = 2000 + 5;
int f[maxl];
char s[maxn][maxl];
void getFail(char* s) {
f[0] = f[1] = 0;
for(int i = 1; s[i]; i++) {
int j = f[i];
while(j && s[i] != s[j]) j = f[j];
f[i+1] = s[i] == s[j] ? j+1 : 0;
}
}
bool match(char* T, char* P) {
int n = strlen(T), m = strlen(P);
getFail(P);
int j = 0;
for(int i = 0; i < n; i++) {
while(j && P[j] != T[i]) j = f[j];
if(P[j] == T[i]) j++;
if(j == m) return true;
}
return false;
}
int main()
{
int T; scanf("%d", &T);
for(int kase = 1; kase <= T; kase++) {
int n; scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%s", s[i]);
int L = 1, R, ans = -1;
for(R = 2; R <= n; R++) {
while(L < R) {
if(match(s[R], s[L])) L++;
else {
ans = R;
break;
}
}
}
printf("Case #%d: %d
", kase, ans);
}
return 0;
}