ccpc宠物对战

Problem - I - Codeforces

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
const long long inf = 0x7f7f7f7f7f7f7f7f;
#define endl '\n'
typedef pair<int,int>pii;
int dp[N][3];
struct node{//字典树 
    int dex=0;
    int d[N][30];
    int cnt[N];
    void insert(string s){
        int x=0;
        for(int i=0;i<s.size();i++){
            if(d[x][s[i]-'a']){//当前结点有的话就按照当前结点顺序走 
                x=d[x][s[i]-'a'];
                continue;
            }
            d[x][s[i]-'a']=++dex;//分配新的结点 
            x=d[x][s[i]-'a'];
        }
        cnt[x]++;
    }
}A,B;
int main(){
    int n,m;
    cin>>n;
    string a,b;
    for(int i=1;i<=n;i++){
        cin>>a;
        A.insert(a);
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b;
        B.insert(b);
    }
    string c;
    cin>>c;
    c=' '+c;
//    for(int i=0;i<=c.size();i++)dp[i][0]=dp[i][1]=inf;
memset(dp,0x3f,sizeof(dp));
    dp[0][1]=0;
    dp[0][0]=0;
    for(int i=1;i<=c.size();i++){
        int x=0;
        for(int j=i;j<=c.size();j++){
            if(A.d[x][c[j]-'a']){
                x=A.d[x][c[j]-'a'];
            }
            else break;
            if(A.cnt[x])dp[j][0]=min(dp[j][0],dp[i-1][1]+1);//由结果倒推 
        }
        x=0;
        for(int j=i;j<=c.size();j++){
            if(B.d[x][c[j]-'a']){
                x=B.d[x][c[j]-'a'];
            }
            else break;
            if(B.cnt[x])dp[j][1]=min(dp[j][1],dp[i-1][0]+1);
        }
    }
    ll op=min(dp[c.size()-1][0],dp[c.size()-1][1]);
    if(op>=1e9)cout<<"-1"<<endl;
    else cout<<op<<endl;
}