Time Limit: 20 Sec
Memory Limit: 256 MB
http://acm.hdu.edu.cn/showproblem.php?pid=5510
Input
The first line contains an integer 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) and in the following n lines list are the strings S1,S2,?,Sn.
All strings are given in lower-case letters and strings are no longer than 2000 letters.
Output
For each test case, output the largest label you get. If it does not exist, output −1.
Sample Input
Sample Output
Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3
题意
你需要找到一个最大的i使得,存在一个在他前面的字符串不是他的子串
题解:
就暴力匹配就好了,然后加一个剪枝,如果这个字符串是某个字符串的子串的话,就不用检查他了(讲道理的话,这个剪枝是没有用的,因为全部都不是子串的话,这个剪枝没有一点卵用。只是数据出水了而已……
正解应该是后缀自动机?AC自动机?
代码
#include<iostream> #include<stdio.h> #include<cstring> using namespace std; char s[550][2005]; int vis[550]; int main() { int t;scanf("%d",&t); for(int cas=1;cas<=t;cas++) { memset(vis,0,sizeof(vis)); int n;scanf("%d",&n); int flag = 0; for(int i=1;i<=n;i++) { scanf("%s",s[i]); for(int j=i-1;j>=1;j--) { if(vis[j])continue; if(strstr(s[i],s[j])==NULL)flag=i; else vis[j]=1; } } if(!flag) printf("Case #%d: -1\n",cas); else printf("Case #%d: %d\n",cas,flag); } }
原文:http://www.cnblogs.com/qscqesze/p/4929963.html