Bazinga HDU - 5510【技巧暴力+字符串】

题目：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[][];

 int main()

 {

     int t,n,cas=;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&n);

         memset(ss,,sizeof(ss));

         for(int i=;i<=n;i++)

             scanf("%s",ss[i]+);

         int ans=-;

         for(int i=n;i>;i--)

         {

             if(!strstr(ss[i]+,ss[i-]+))

             {

                 ans=max(ans,i);

                 for(int j=i+;j<=n;j++)

                 {

                     if(!strstr(ss[j]+,ss[i-]+))

                         ans=max(ans,j);

                 }

             }

         }

         printf("Case #%d: %d\n",++cas,ans);

     }

     return ;

 }

巴特西

Bazinga HDU - 5510【技巧暴力+字符串】

最新文章

热门文章