来一发代码,先前后两两比较,如果前一个串是后一个串的字串,那他就是没必要的,假设第i个串是i+1的子串,如果在后面循环比较中,如果第i+1个串是后面串的子串,那i个串就没有比的必要了,如果第i+1不是后面串的子串,直接结束循环,查找结束,得出结果
#include <bits/stdc++.h>
int next[10005];
int T;
char s[505][2005];
bool v[550],flag;
void getnext(char str[],int len)
{
int k=0;
next[1]=0;
for(int i=2;i<=len;i++)
{
while(k>0&&str[k+1]!=str[i])
k=next[k];
if(str[k+1]==str[i])
k++;
next[i]=k;
}
}
int match(char P[],int lenp,char T[],int lent)
{
int res=0;
getnext(P,lenp);
int k=0;
for(int i=1;i<=lent;i++)
{
while(k>0&&P[k+1]!=T[i])
k=next[k];
if(P[k+1]==T[i])
k++;
if(k==lenp){
res++;
k=next[k];//这儿修改很重要,不然会超时
return 1;
}
}
return 0;
}
int main()
{
scanf("%d",&T);
int n;
for(int cs = 1;cs<=T;cs++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
memset(v,true,sizeof(v));
int sum = 0;
for(int i=2;i<=n;i++)
{
int lent=strlen(s[i]+1);
int lenp=strlen(s[i-1]+1);
if(match(s[i-1],lenp,s[i],lent))
v[i-1]=false;
}
printf("Case #%d: ",cs);
flag = false;
for(int i=n;i>=1&&!flag;i--)
{
for(int j=i-1;j>=1&&!flag;j--)
{
if(v[j])
{
int lenw=strlen(s[j]+1);
int lent=strlen(s[i]+1);
int ans=match(s[j],lenw,s[i],lent);
if(ans==0)
{
printf("%d\n",i);
flag = true;
break;
}
}
}
}
if(!flag) printf("-1\n");
}
//system("pause");
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
蟠桃记 1 折线分割平面 2 不容易系列之一 2 骨牌铺方格 3 不容易系列之(3)—— LELE的RPG难题 3 Children’s Queue 3 献给杭电五十周年校庆的礼物 3 钥匙计数之二 3 钥匙计数之一 3 母牛的故事 3 ...
很多经典的杭电oj与poj习题的ac代码与详解!全部ac,决对没有错误的代码!
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU 1022 Train Problem I 附详细思路
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告