【NOIP2017模拟12.3】子串

题目

分析

对于当前枚举串 (now)，从前往后扫。若扫到 (i)，(s_i) 是 ; (s_j) 的子串 ((i < j < now))，我们就可以跳过不匹配 (i)。因为如果(s_i)是(s_j) 的子串，那么(s_j)如果是(s_now)的子串，其实就不需要比较(s_i)和(s_now)。若不存在这样的 (j)，匹配即可，若 (s_i)是 (snow) 的子串，(i) 之后就可以跳过了 (打个标记,或者用双向链表)；否则 (now) 就可以更新答案，然后break。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const int N=505;
using namespace std;
char s[N][N*4];
int next[N*4],t,n,ans,bz[N],len[N];
bool kmp(int x,int y)
{
	long long j=0;
	memset(next,0,sizeof(next));
	for(long long i=2;i<=len[y];i++)
	{
		while(j && s[y][i]!=s[y][j+1]) j=next[j];
		if(s[y][j+1]==s[y][i]) j++;
		next[i]=j;
	}
	j=0;
	for(long long i=1;i<=len[x];i++)
	{
		while(j && s[x][i]!=s[y][j+1]) j=next[j];
		if(s[y][j+1]==s[x][i]) j++;
		if(j==len[y]) return true;
	}
	return false;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) 
		{
			scanf("%s",s[i]+1);
			len[i]=strlen(s[i]+1);
		}
		ans=0;
		memset(bz,true,sizeof(bz));
		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<=i-1;j++)
			if(bz[j])
			{
				if(kmp(i,j)) bz[j]=false;
				else 
				{
					ans=i;
					break;
				}
			}
		}
		if(!ans) cout<<-1<<endl;
		else cout<<ans<<endl;
	}
}