LG2292 L语言

题意

给出\(n\)个单词，再给出\(m\)段无符号的文章，询问每段文章能最长匹配的前缀。

思路

设\(f[i]\)为前缀\([1,i]\)能否被匹配，对于一个可以匹配完的节点\(i\)，若有\([i+1,j]\)此个单词，那么\(f[j]\)也为真。可以将模式串插入到一个\(Trie\)中，然后在\(Trie\)中查找。而事实上，对于每一个\(i\),不需要枚举\(j\)再验证是否匹配，只需要沿\(i+1\)、\(i+2\)……在\(Trie\)树上跑一次，然后每遇到一个单词结尾就转移一个\(j\),这样子就很快了

#include <bits/stdc++.h>

int trie[1000005][26],val[1000005],f[1000005],cnt,n,m;

char s[1000005],word[1000005];

void insert(){

	int u=0,l=strlen(word+1);

	for (int i=1;i<=l;i++){

		if (!trie[u][word[i]-'a']) trie[u][word[i]-'a']=++cnt;

		u=trie[u][word[i]-'a'];

	}

	val[u]=1;

}

void solve(){

	int u=0,l=strlen(word+1);

	memset(f,0,sizeof(f));

	f[0]=1;

	for (int i=1;i<=l;i++)

	if (f[i-1]){

		int j=i,u=trie[0][word[i]-'a'];

		while (u && j<=l){

			if (val[u]) f[j]=1;

			u=trie[u][word[++j]-'a'];

		}

	}

	for (int i=l;i>=0;i--)

	if (f[i]){

		printf("%d\n",i);

		return;

	}

}

int main(){

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++){

		scanf("%s",word+1);

		insert();

	}

	for (int i=1;i<=m;i++){

		scanf("%s",word+1);

		solve();

	}

	return 0;

}

巴特西

LG2292 L语言

题意

思路

最新文章

热门文章