CF633C：Spy Syndrome 2—

CF633C：Spy Syndrome 2——题解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int M=1001000;
int n,m,dp[M],l[M],tot=1,now,ll,pos[M];
char s[M],t[M];
vector<int>v;
struct node{
    int ed,son[26];
    node(){
        ed=0;
        memset(son,0,sizeof(son));
    }
}tree[1000001];
void insert(int k){
    now=1;
    int q;
    for(int i=ll+1;i<=l[k]+ll;i++){
    if(t[i]<'a')q='a'-'A';else q=0;
    if(tree[now].son[t[i]-'a'+q]==0){
        tot++;
        tree[now].son[t[i]-'a'+q]=tot;
    }
    now=tree[now].son[t[i]-'a'+q];
    }
    tree[now].ed=k;
    return;
}
int main(){
    cin>>n;
    cin>>s+1;
    cin>>m;
    for(int i=1;i<=m;i++){
    cin>>t+ll+1;
    pos[i]=ll+1;
    l[i]=strlen(t+ll+1);
    insert(i);
    ll+=l[i];
    }
    dp[0]=1;
    for(int i=1;i<=n;i++){
    now=1;
    for(int j=1;j<=i&&now;j++){
        now=tree[now].son[s[i-j+1]-'a'];
        if(tree[now].ed&&dp[i-j]){
        dp[i]=tree[now].ed;
        break;
        }
    }
    }
    for(int i=n;i>=1;i-=l[dp[i]]){
    v.push_back(dp[i]);
    }
    int ss=v.size();
    for(int i=ss-1;i>=0;i--){
    for(int j=1;j<=l[v[i]];j++){
        putchar(t[pos[v[i]]+j-1]);
    }
    putchar(' ');
    }
    return 0;
}