博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU_5510_Bazinga
阅读量:5257 次
发布时间:2019-06-14

本文共 2666 字,大约阅读时间需要 8 分钟。

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 5056    Accepted Submission(s): 1596

Problem 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 (1in) such that there exists an integer j (1j<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 (1t50) which is the number of test cases.
For each test case, the first line is the positive integer n (1n500) 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
 

 

Source
 
  • 找到最大ID字符串i使得存在j<i的字符串不是i的子串
  • 首先考虑如果从l到r串都满足都是r的子串,那么k>r串只需要检测r串即可
  • 如果自l串开始到l+k串都是存在小于l的串不是当前串子串,那么对于l+k+1串就要检测l-1串和l到l+k串
  • 算法出来了,就是记录当前最大id使得此id之前全是id串的子串,然后检测串的范围就是这个id到当前ID的前一位
  • 如果用这样的算法,用c的strstr即可,用kmp可以减少一半时间

 

 

1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 using namespace std;14 typedef long long LL ;15 typedef unsigned long long ULL ;16 const int maxn = 1e5 + 10 ;17 const int inf = 0x3f3f3f3f ;18 const int npos = -1 ;19 const int mod = 1e9 + 7 ;20 const int mxx = 100 + 5 ;21 const double eps = 1e-6 ;22 const double PI = acos(-1.0) ;23 24 int T, n, use[maxn], mx, ans;25 char s[505][2005];26 std::vector
v;27 int main(){28 // freopen("in.txt","r",stdin);29 // freopen("out.txt","w",stdout);30 while(~scanf("%d",&T)){31 for(int kase=1;kase<=T;kase++){32 ans=-1;33 scanf("%d",&n);34 mx=1;35 use[1]=0;36 v.clear();37 scanf("%s",s[1]);38 for(int i=2;i<=n;i++){39 scanf("%s",s[i]);40 int flag=1;41 if(strstr(s[i],s[mx])==NULL)42 flag=0;43 if(flag&&use[i-1]){44 for(int j=v.size()-1;j>=0 && flag;j--){45 if(strstr(s[i],s[v[j]])==NULL)46 flag=0;47 }48 }49 if(flag){50 mx=i; use[i]=0; v.clear();51 }else{52 ans=i; use[i]=1; v.push_back(i);53 }54 }55 56 printf("Case #%d: %d\n",kase,ans);57 }58 }59 return 0;60 }

 

 

 

转载于:https://www.cnblogs.com/edward108/p/7639192.html

你可能感兴趣的文章
源代码的下载和编译读后感
查看>>
Kafka学习笔记
查看>>
Octotree Chrome安装与使用方法
查看>>
Windows 环境下基于 Redis 的 Celery 任务调度模块的实现
查看>>
趣谈Java变量的可见性问题
查看>>
C# 强制关闭当前程序进程(完全Kill掉不留痕迹)
查看>>
ssm框架之将数据库的数据导入导出为excel文件
查看>>
语音识别中的MFCC的提取原理和MATLAB实现
查看>>
验证组件FluentValidation的使用示例
查看>>
0320-学习进度条
查看>>
解决windows系统的oracle数据库不能启动ora-00119和ora-00130的问题
查看>>
ip相关问题解答
查看>>
MetaWeblog API Test
查看>>
反弹SHELL
查看>>
关闭Chrome浏览器的自动更新和升级提示
查看>>
移动、尺寸改变
查看>>
poj2255Tree Recovery【二叉树重构】
查看>>
tcpcopy 流量复制工具
查看>>
vue和react的区别
查看>>
第十一次作业
查看>>