【洛谷P2292】L语言

佚名 6年前 (2019-05-07) 随笔 1282人围观抢沙发百度已收录

题目大意：给定一个长度为 N 的字符串和一个字典，字典中所有的字符串的长度均不超过 10，求给定的字符串从前往后最多有多少位可以与字典匹配。

题解：设 \(dp[i]\) 表示串的前 i 位是否能够与字典匹配，若 \(dp[i]=1\)，则对 s[i+1,~] 部分与字典进行匹配，即：对可以匹配的最大长度进行拓展。由于字典中每个串的长度很小，一次拓展最多只会执行 10 次运算，因此总的复杂度为 \(O(10*N*M)\)。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;

int trie[200][26],tot=1,ed[maxn];
int n,m,dp[maxn];
char s[20],S[maxn];

void insert(char *ss){
    int len=strlen(ss+1),now=1;
    for(int i=1;i<=len;i++){
        int ch=ss[i]-'a';
        if(!trie[now][ch])trie[now][ch]=++tot;
        now=trie[now][ch];
    }
    ed[now]=1;
}
void find(char *ss){
    memset(dp,0,sizeof(dp));
    int len=strlen(ss+1),ans=0;
    dp[0]=1;
    for(int i=0;i<=len;i++)if(dp[i]){
        int now=1;
        for(int j=i+1;j<=len;j++){
            int ch=ss[j]-'a';
            if(!trie[now][ch])break;
            now=trie[now][ch];
            if(ed[now])dp[j]=1,ans=max(ans,j);
        }
    }
    printf("%d\n",ans);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",s+1),insert(s);
    for(int i=1;i<=m;i++)scanf("%s",S+1),find(S);
    return 0;
}