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语言

原文：https://www.cnblogs.com/flyfeather6/p/10662839.html