题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5510
题意：给出n个字符串S1~Sn，让找出最大的i使得对于字符串Si，存在一个字符串Sj（1≤j＜i）不是Si的子串。
解析：要解这道题考的更多的是靠思维而不是字符串知识，避免超时的要点就是：如果Sj是Si的父串，Sk是Sj的父串，那么Sk一定是Si的父串。
有思路如下：考虑下标连续的字符串Si~Sj，其中Si是Si+1的子串，Si+1是Si+2的子串。。。那么考虑它们为一个整体。现在找到以Sn为结尾的这样一个整体Sl~Sn，那么Sl-1就不是Sl的子串，所以Sl为当前找到的满足题目要求最小的答案记为Sl。接下来就是暴力了，直接枚举Sl-1到S1的字符串，如果某个枚举到某个字符串不是Sl+1的子串，那么可以更新答案到Sl+1，以此类推去更新更大的答案。
求子串可用如下函数，复杂度O（Len1*Len2）：
代码（103ms）：
#include<bits/stdc++.h>
using namespace std;
char str[505][2005];
int main()
{int T,n,cas=0;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%s",str[i]);int low=n;while(low>=1&&strstr(str[low],str[low-1])!=NULL) low--;if(low==0) low++;//low为最小可能答案for(int i=low-1;i>=1&&low<=n;i--)//枚举{while(low<n&&strstr(str[low+1],str[i])==NULL) low++;//看i是不是low+1的子串}if(low==1) low=-1;printf("Case #%d: %d\n",++cas,low);}return 0;
}另外有更暴力的方法，就是暴力每一个字符串看它有没有子串，但进行一些剪枝：若果某个字符串Si存在父串Sf，那么我们不用再看它（Si）是不是其它串的子串，因为如果Sf不是某个串的子串，那么Si也不可能是这个串的子串。
代码（109ms）：
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2005;int n,fa[MAXN];
char str[505][MAXN];int main()
{int T,cas=0;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%s",str[i]),fa[i]=0;int ans=-1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(fa[j]==1) continue;if(strstr(str[i],str[j])==NULL) {ans=i;break;}else fa[j]=1;}}printf("Case #%d: %d\n",++cas,ans);}return 0;
}另外，用KMP处理字符串匹配如下，代码（222ms）：
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2005;int n;
char str[505][MAXN];
int nex[505][MAXN],nex2[505],fa[MAXN];void getNext(int son)
{int lenw=strlen(str[son]);nex[son][0]=nex[son][1]=0;nex2[0]=nex2[1]=0;for(int i=1;i<lenw;i++){int j=nex2[i];while(j&&str[son][i]!=str[son][j])j=nex2[j];nex2[i+1]=nex[son][i+1]=(str[son][i]==str[son][j])?j+1:0;if(nex[son][i+1]==j+1&&str[son][i+1]==str[son][j+1])nex[son][i+1]=nex[son][j+1];}
}int getKMP(int son,int fa)
{int lenw=strlen(str[son]);int lent=strlen(str[fa]);//getNext(son);int j=0;for(int i=0;i<lent;i++)//i fa{while(j&&str[son][j]!=str[fa][i])j=nex[son][j];if(str[son][j]==str[fa][i])j++;if(j==lenw)return 1;}return 0;
}int main()
{int T,cas=0;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%s",str[i]);for(int i=1;i<=n;i++)//预处理所有串的Next数组getNext(i),fa[i]=0;int ans=-1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(fa[j]==1) continue;if(getKMP(j,i)==0) {ans=i;break;}elsefa[j]=1;}}printf("Case #%d: %d\n",++cas,ans);}return 0;
}