题目

分析

对于当前枚举串 \(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;

	}

}

巴特西

【NOIP2017模拟12.3】子串

题目

分析

最新文章

热门文章