HDOJ 5510 Bazinga 【2015沈阳现场赛】字符串

n(1n500)个字符串,求一个最大的i,使得存在一个Sj不是Si的子串。


这个题,用不用KMP其实意义不是太大,重点是如何把二维的循环减小到一维

跟二分答案的思路差不多:


维护两个指针l,r


那么有两种情况:

如果SlSr的子串,那么l++。

如果 Sl不是是 Sr 的子串,那么将答案更新为 r ,然后 r++

考虑Sr+1的时候为什么同样不考虑Sl之前的串了呢?

因为 Sl 之前的串都是后面某个串的子串,所以如果他们中有不是 Sr+1 子串的串的话,那么一定有对应的那个串也不是 Sr+1 的子串。这样保证 r 一定能更新到 ans


如何去判断是不是匹配反而不是那么难

KMP可以,strstr这个函数也可以

代码如下:

#include<bits/stdc++.h>
using namespace std;

const int maxn=650;
int n;
char a[maxn][maxn*10];
bool b[maxn];

int main(){
	//freopen("input.txt","r",stdin);
	int T;
	scanf("%d",&T);
	for(int Case=1;Case<=T;Case++){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%s",a[i]);
		for(int i=1;i<=n;i++) b[i]=false;
		int ans=-1;
		for(int i=1;i<n;i++)
			for(int j=i+1;j<=n;j++)
				if (b[j]==false){
					if (strstr(a[j],a[i])!=NULL) break;
					else{
						b[j]=true;
						ans=max(ans,j);
					}
				}
		printf("Case #%d: %d\n",Case,ans);
	}
	return 0;
}


全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务