废话：
这道题很是花了我一番功夫。首先，我不会kmp算法，还专门学了一下这个算法。其次，即使会用kmp，但是如果暴力枚举的话，还是毫无疑问会爆掉。因此在dfs的基础上加上两次剪枝解决了这道题。
题意：
我没有读题，只是队友给我解释了题意，然后我根据题意写的题。
大概意思是给n个字符串，从上到下依次标记为1——n，寻找一个标记最大的串，要求这个串满足：标记比它小的串中至少有一个不是它的子串。
输入：
第一行输入一个整型t，表示共有t组数据。
每组数据首行一个整型n，表示有n个串。
接下来n行，每行一个字符串。
输出：
输出格式为”Case #x: y”，其中x为组数，y表示串的标记。
如果存在满足条件的串，则输出这个串的标记，否则输出-1。
题解：
- 使用dfs，源串从标记最大的串（串n-1）开始，匹配串从比源串小的串开始，从大到小依次匹配。
- 如果两个串匹配，则继续匹配更小的匹配串。如果两个串不匹配，则记录不匹配的匹配串，同时比较源串和答案的大小，答案取较大值，同时执行3。如果匹配串直到匹配到标记最小的串（串0），所有串都可以和源串匹配，则执行4。
- 源串回溯，然后用回溯的源串和记录的匹配串进行比较，即，进行2。
- 当前源串不满足条件，回溯到dfs结束。
- 输出答案。
需要注意的有两点——
- 如果当前源串Aj与当前匹配串Ai不匹配，那么可知当前源串的父串Ak，即当前源串的源串，也可以直接与Ai比较，而不需要与Aj和Ai之间的串匹配，因为Al(i < l < j) 一定是Ak的子串。这点很容易证明。
- 如果源串Ak一直递归到最小的串A0都匹配，那么任意串Ai(0 < i <= k) 都和A0匹配，即A0是任意串Ai的子串。那么任意Ai都不可能是答案。
代码如下——
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int N = ; int Next[N];
char s[][N];
int t, n;
int lenS, lenT;
int ans;
int mid; //剪枝，放置某个串被多次访问 void init()
{
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%s", s[i]);
ans = -;
mid = -;
} void kmpNext(char* T) //计算Next数组
{
int i = ;
Next[] = -;
while(i < lenT)
{
int j = ;
while(T[j] == T[i])
{
Next[i] = j;
i++;
j++;
}
Next[i] = j;
i++;
}
} bool kmp(char* S, char* T) //kmp算法
{
lenS = strlen(S);
lenT = strlen(T);
kmpNext(T);
int i = , j = ;
while(i < lenS && j < lenT)
{
if(j == -)
{
i++;
j = ;
}
else if(S[i] == T[j])
{
i++;
j++;
}
else j = Next[j];
}
if(j == lenT) return ;
return ;
} bool dfs(int x) //递归寻找子串
{
for(int i = x-; i >= ; i--)
{
if(mid != - && mid != i) continue; //剪枝,如果串Ai从未查询过，或者串Ax的子串含不串Ai，那么查询Ax是否含Ai
if(kmp(s[x], s[i]))
{
if(i == ) return ;
mid = -; //如果串Ax含串Ai，那么mid归为-1
bool flag = dfs(i);
if(flag) return ; //剪枝，如果串A0是串Ax的子串，那么Ax不符合条件
}
else
{
ans = ans > x ? ans : x; //永远取最大值
mid = i;
break;
} }
return ;
} void work()
{
dfs(n-);
} void outit(int tm)
{
printf("Case #%d: %d\n", tm, ans+);
} int main()
{
scanf("%d", &t);
for(int tm = ; tm <= t; tm++)
{
init();
work();
outit(tm);
}
}
Kmp算法——
http://www.cnblogs.com/mypride/p/4950245.html
ps. 看了看别人的代码，有些直接用了迭代法，复杂度为n^2/2，不过加上了一个感觉不太靠谱的剪枝。我算了算，最坏情况下时间好像还有可能爆掉。但是运行结果竟然不比我的慢多少，醉了。可能我算时间的方法有问题？或者数据特殊？
唉……革命尚未成功，同志仍需努力啊！