首页 > 其他 > 详细

HDU 5510 Bazinga 暴力匹配加剪枝

时间:2015-11-02 15:21:47      阅读:323      评论:0      收藏:0      [点我收藏+]

Bazinga

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5510

Description

Ladies and gentlemen, please sit up straight.
Don‘t tilt your head. I‘m serious.
技术分享

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) and Sj is not a substring of Si.

A substring of a string Si is another string that occurs in Si. For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

Input

The first line contains an integer t (1≤t≤50) 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.

Output

For each test case, output the largest label you get. If it does not exist, output −1.

Sample Input

4
5
ab
abc
zabc
abcd
zabcd
4
you
lovinyou
aboutlovinyou
allaboutlovinyou
5
de
def
abcd
abcde
abcdef
3
a
ba
ccc



Sample Output

Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3

HINT

 

题意

你需要找到一个最大的i使得,存在一个在他前面的字符串不是他的子串

题解:

就暴力匹配就好了,然后加一个剪枝,如果这个字符串是某个字符串的子串的话,就不用检查他了(讲道理的话,这个剪枝是没有用的,因为全部都不是子串的话,这个剪枝没有一点卵用。只是数据出水了而已……

正解应该是后缀自动机?AC自动机?

代码

 

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

char s[550][2005];
int vis[550];
int main()
{
    int t;scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        memset(vis,0,sizeof(vis));
        int n;scanf("%d",&n);
        int flag = 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s[i]);
            for(int j=i-1;j>=1;j--)
            {
                if(vis[j])continue;
                if(strstr(s[i],s[j])==NULL)flag=i;
                else vis[j]=1;
            }
        }
        if(!flag)
            printf("Case #%d: -1\n",cas);
        else
            printf("Case #%d: %d\n",cas,flag);
    }
}

 

HDU 5510 Bazinga 暴力匹配加剪枝

原文:http://www.cnblogs.com/qscqesze/p/4929963.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!