HDU 5510 Bazinga 暴力匹配加剪枝
Bazinga
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5510
Description
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
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[][];
int vis[];
int main()
{
int t;scanf("%d",&t);
for(int cas=;cas<=t;cas++)
{
memset(vis,,sizeof(vis));
int n;scanf("%d",&n);
int flag = ;
for(int i=;i<=n;i++)
{
scanf("%s",s[i]);
for(int j=i-;j>=;j--)
{
if(vis[j])continue;
if(strstr(s[i],s[j])==NULL)flag=i;
else vis[j]=;
}
}
if(!flag)
printf("Case #%d: -1\n",cas);
else
printf("Case #%d: %d\n",cas,flag);
}
}
最新文章
- 基于HTML5的WebGL应用内存泄露分析
- sublime通用快捷键 汉化 安装 插件
- [转]ORACLE 审计功能
- 11.python之线程,协程,进程,
- Azure HDInsight 现已在中国正式发布
- [XMPP]简易的聊天室实现[一]
- Ubuntu 如何重新安裝 Unity ?
- MySQL性能优化方案
- 你必须知道的session与cookie
- Android初级教程理论知识(第五章页面跳转和数据传递)
- js方法实现--上传文件功能
- 【论文速读】Shitala Prasad_ECCV2018】Using Object Information for Spotting Text
- 论文阅读:Siam-RPN
- 第三节:带你详解Java的操作符,控制流程以及数组
- Spring Aop 修改目标方法参数和返回值
- find -exec 批量使用方法
- MySQL开发——【数据的基本操作】
- ubuntu系统下安装pyspider:使用supervisord启动并管理pyspider进程配置及说明
- JDK源码分析(五)——HashSet
- HDU - 6406 Taotao Picks Apples (RMQ+dp+二分)
热门文章
- 《C++ Primer 4th》读书笔记 第6章-语句
- Android 使用库项目时的一个特殊tip
- 转载RabbitMQ入门(2)--工作队列
- 怎么制作生成苹果手机app应用的下载二维码图片
- xcode升级,报错 libxml/tree.h not found (Xcode4.6解决方案)
- Using Open Source Static Libraries in Xcode 4
- SharePoint 2010 列表项事件接收器 ItemAdded 的使用方法
- hdu 5335 Walk Out(bfs+斜行递推) 2015 Multi-University Training Contest 4
- Java中的10颗语法糖
- HDU 2227-Find the nondecreasing subsequences(dp+BIT优化)