Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.
For nn given strings S1,S2,⋯,SnS1,S2,⋯,Sn, labelled from 11 to nn, you should find the largest i (1≤i≤n)i (1≤i≤n)such that there exists an integer j (1≤j<i)j (1≤j<i) and SjSj is not a substring of SiSi.
Don't tilt your head. I'm serious.
For nn given strings S1,S2,⋯,SnS1,S2,⋯,Sn, labelled from 11 to nn, you should find the largest i (1≤i≤n)i (1≤i≤n)such that there exists an integer j (1≤j<i)j (1≤j<i) and SjSj is not a substring of SiSi.
A substring of a string SiSi is another string that occurs in SiSi. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".
InputThe first line contains an integer t (1≤t≤50)t (1≤t≤50)which is the number of test cases.
For each test case, the first line is the positive integer n (1≤n≤500)n (1≤n≤500) and in the following nn lines list are the strings S1,S2,⋯,SnS1,S2,⋯,Sn.
All strings are given in lower-case letters and strings are no longer than 20002000 letters.OutputFor each test case, output the largest label you get. If it does not exist, output −1−1.Sample Input
4
5
ab
abc
zabc
abcd
zabcd
4
you
lovinyou
aboutlovinyou
allaboutlovinyou
5
de
def
abcd
abcde
abcdef
3
a
ba
ccc
Sample Output
Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3 这题用hash预处理 然后用vector从上到下扫过去
类似于维护当前未匹配的序列
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <set>
#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-6
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define bug printf("******\n")
#define mem(a,b) memset(a,b,sizeof(a))
#define fuck(x) cout<<"["<<x<<"]"<<endl
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define pf printf
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define FIN freopen("DATA.txt","r",stdin)
#define gcd(a,b) __gcd(a,b)
#define lowbit(x) x&-x
#pragma comment (linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x7fffffff;
const int maxn = 5e4 + ;
ULL HASH[], seed = , p[], mp[][];
char s2[],a[][];
int t, n;
void init() {
p[] = ;
for (int i = ; i <= ; i++)
p[i] = p[i - ] * seed;
}
int check(int i, int j) {
int len1 = strlen(a[i]), len2 = strlen(a[j]);
for (int k = ; k <= len1 - len2 ; k++){
if (mp[i][k + len2] - mp[i][k]*p[len2] == HASH[j]) return ;
}
return ;
}
int main() {
init();
int cas=;
sf(t);
while(t--) {
sf(n);
for (int i = ; i <= n ; i++) {
scanf("%s", a[i]);
int len = strlen(a[i]);
int top = ;
mp[i][] = ;
for (int j = ; j < len ; j++) {
s2[top++] = a[i][j];
mp[i][top] = mp[i][top - ] * seed + a[i][j];
}
HASH[i] = mp[i][top];
}
int ans=-;
vector<int>s;
s.clear();
s.push_back();
for (int i= ;i<=n ;i++) {
while(s.size()) {
if ( check(i,s[s.size()-]) ) s.pop_back();
else break;
}
s.push_back(i);
if (s.size()>) ans=i;
}
printf("Case #%d: %d\n",cas++,ans);
}
return ;
}