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

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

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

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

维护两个指针l,r

那么有两种情况：

如果Sl是Sr的子串，那么l++。

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

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

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;
}