题目描述
For n given strings S1 , S2 , … , Sn , labelled from 1 to n, you should find the largest i (1 ≤ i ≤ n) such that there exists an integer j (1 ≤ j < i) such that Sj is not a substring of Si . For example, “izh” is a substring of “ruizhang”,and “zrui” is not a substring of “ruizhang”.
输入
The first line contains an integer t (1 ≤ t ≤ 100) 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.
输出
For each test case, output the largest label you get. If it does not exist,
output −1.
样例输入
3
4
aa
ab
aba
aaba
5
a
ba
acba
abaaacaabaa
dabadaacasabaza
3
a
ba
ccc
样例输出
Case #1: 2
Case #2: -1
Case #3: 3
题意： 输入n个串，输出一个i，表示第i个串之前的串存在一个串不是i串的子串，使得i最大。
因为串长和串数较多，因此直接一个一个串裸的比较一定会超时。可以这样考虑，对于一个串，在此之前若是有大量的串是其子串，那么一定会存在某个较长串包含了大量的子串，我们一旦比较了某个较长子串，其中包含了更早之前的子串子串，这样就不必比较子串的子串了。相当于比较一个顶十个。
那么如何找到这个包含子串的子串呢。
用并查集实现，再向前暴力查找时，若一个串是其子串，那么并查集加入集合。否则直接更新ans，并且break掉进行下一个串的查询，之后的串都可以利用这个并查集的信息来比较所有集合中最长的串，使得较短的子串不会被重复比较。因为在较长串中就已经知道其是不是自己的子串。
同样的思想也可以用队列实现，队列里保存了几个将要用于比较的最长子串，这样可以过滤掉很多不必要的子串的子串比较。
#include<stdio.h>///并查集优化子串查找
#include<string.h>
int z[508];
char a[508][2008];
int find(int x)
{
int r=x,k;
while(z[r]!=r)
{
k=r;
r=z[r];
z[k]=z[r];
}
return r;
}
void join(int x,int y)
{
int aa=find(x),bb=find(y);
if(aa!=bb)
{
if(strlen(a[x])<strlen(a[y]))
{
z[x]=y;
}
else
z[y]=x;
}
}
int main()
{
int t,i,j,n,cas=0;
scanf("%d",&t);
while(t--)
{
cas++;
int ans=-1;
scanf("%d",&n);
for(i=1;i<=n;i++)z[i]=i;
for(i=1;i<=n;i++)
{
scanf("%s",a[i]);
bool flag=false;
for(j=i-1;j>=1;j--)
{
if(find(i)==find(j))
continue;
if(strstr(a[i],a[j])==NULL)
{
flag=true;
break;
}
else
join(i,j);
}
if(flag)ans=i;
}
printf("Case #%d: %d
",cas,ans);
}
}