Bazinga HDU

题目：https://vjudge.net/problem/HDU-5510

$2015ACM/ICPC$ 亚洲区沈阳站

题目大意：

输入$t$（表示样例个数）

如何每个样例一个 $n$，表示字符串的个数。

接下来 $n$个字符串，题目要求输出一个最大的i，使得对于标号为 $j (1<=j<i)$ 的字符串 $ss[j]$ 不是字符串 $ss[i]$ 的子串。

思路：

从最后一个字符串向前枚举，如果对于一个字符串 $ss[i]$，其前面的一个字符串 $ss[i-1]$ 不是 $ss[i]$ 的子串，那么就从 $i+1$ 开始向后寻找最大的不包含 $ss[i-1]$ 的字符串。

判断子串的过程可以用函数 $strstr(s_1,s_2)$:如果 $s_2$ 不是 $s_1$ 的子串，那么返回 $null$。

也可以用 $kmp$。

#include <bits/stdc++.h>
using namespace std;
char ss[505][2005];
int main()
{
    int t,n,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(ss,0,sizeof(ss));
        for(int i=1;i<=n;i++)
            scanf("%s",ss[i]+1);
        int ans=-1;
        for(int i=n;i>1;i--)
        {
            if(!strstr(ss[i]+1,ss[i-1]+1))
            {
                ans=max(ans,i);
                for(int j=i+1;j<=n;j++)
                {
                    if(!strstr(ss[j]+1,ss[i-1]+1))
                        ans=max(ans,j);
                }
            }
        }
        printf("Case #%d: %d
",++cas,ans);
    }
    return 0;
}