Spy Syndrome 2 题解(dp+hash)

题目链接

题目思路

这个题目算是一个经典的dp

设表示以i结尾的最后一个字符串的序列是

hash预处理

然后计算答案直接回溯即可

复杂度

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5,inf=0x3f3f3f3f,base=233;
const double eps=1e-3;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m;
int dp[maxn];
char s[maxn];
int len[maxn];
unordered_map<ull,int> mp;
char str[maxn][1000+5];
ull a[maxn];
ull pre[maxn],power[maxn];
ull get_hash(int l,int r){
    return pre[r]-pre[l-1]*power[r-l+1];
}
void dfs(int pos){
    if(pos==0) return ;
    dfs(pos-len[dp[pos]]);
    printf("%s ",str[dp[pos]]+1);
}
signed main(){
    scanf("%d %s",&n,s+1);
    power[0]=1;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]*base+s[i]-'a'+1;
        power[i]=power[i-1]*base;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%s",str[i]+1);
        len[i]=strlen(str[i]+1);
        for(int j=len[i];j>=1;j--){
            a[i]=a[i]*base+str[i][j]-'a'+1;
            if(str[i][j]<'a'){
                a[i]=a[i]+'a'-'A';
            }
        }
        mp[a[i]]=i;
    }
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(dp[j-1]!=-1&&mp.count(get_hash(j,i))){
                dp[i]=mp[get_hash(j,i)];
            }
        }
    }
    dfs(n);
    return 0;
}