题解：P16827 [AFOI 2025] D.谐音替换

· · 题解

十分钟会了，最后写的时候把整段分成三段写成一个前缀分成三段了且没什么时间调了，导致赛时没过。

题意：

给定 n 个字符串，有 m 个询问，每次给定一个字符串，问你有多少种分段方式使得这个串可以被分成三段，且这三段要么是 n 个字符串中某个串的前缀，要么是某个串的后缀。

做法：

我们首先会想一个暴力 DP 做法，我们知道 DP 是有两种写法的，自己转移后面，或者自己被前面转移，我们从这里得到启发，我们发现转移后面相当于在一个前缀上加字母，被前面转移相当于往左走的时候在后缀上加字母，且我们知道前后缀是存在单调性的，于是我们考虑结合两种做法。

首先我们先把前面 n 个串的前后缀哈希一下然后分别存起来，然后询问的时候先对询问串做一遍哈希。

代码很好写都是复制粘贴的。

#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
using namespace std;
const int MAXN=5e5+10;
const int base=131311;
int n,m,len;
struct BIT{
    int t[MAXN];
    int lowbit(int x){return x&-x;}
    void add(int x,int y){
        for(int i=x;i<=len;i+=lowbit(i)) t[i]+=y;
    }
    int sum(int x){
        int res=0;
        if(!x) return 0;
        for(int i=x;i;i-=lowbit(i)) res+=t[i];
        return res;
    }
    void clear(){
        for(int i=1;i<=len;i++) t[i]=0;
    }
}bit,bit2;
unordered_map<ull,bool>pre,suf;
ull Pre[MAXN],pw[MAXN];
ull get_hash(int l,int r){
    return Pre[r]-Pre[l-1]*pw[r-l+1];
}
vector<int>Add[MAXN],Del[MAXN];
int vis[MAXN],s[MAXN];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    cin>>n>>m;pw[0]=1;
    for(int i=1;i<=MAXN-10;i++) pw[i]=pw[i-1]*base;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        ull hs=0;
        for(int j=0;j<s.size();j++){
            hs=hs*base+s[j];pre[hs]=1;
        }hs=0;ull P=1;
        for(int j=s.size()-1;j>=0;j--){
            hs=hs+P*s[j];suf[hs]=1;P*=base;
        }
    }
    for(int i=1;i<=m;i++){
        string t;cin>>t;t=" "+t;len=t.size()-1;
        bit.clear();bit2.clear();
        for(int j=1;j<=len;j++){
            s[j]=0;vis[j]=0;
            Pre[j]=Pre[j-1]*base+t[j];
            if(pre[Pre[j]]||suf[Pre[j]]) bit.add(j,1),vis[j]=1;
        }
        for(int j=1;j<len-1;j++){
            if(vis[j]){
                int l=j+1,r=len-1,num=j;
                while(l<=r){
                    int mid=l+r>>1;
                    if(pre[get_hash(j+1,mid)]) num=mid,l=mid+1;
                    else r=mid-1;
                }   
                if(num>j) Add[j+1].push_back(j),Del[num].push_back(j);
            }vis[j]=0;
        }
        for(int j=2;j<len;j++){
            for(auto x:Add[j]) bit2.add(x,1);
            int l=2,r=j,num=j+1;
            while(l<=r){
                int mid=l+r>>1;
                if(suf[get_hash(mid,j)]) num=mid,r=mid-1;
                else l=mid+1;
            }
            s[j]=bit2.sum(num-2);
            s[j]+=bit.sum(j-1)-bit.sum(num-2);
            for(auto x:Del[j]) bit2.add(x,-1);
            Add[j].clear();Del[j].clear();
        }bit2.clear();bit.clear();
        for(int j=2;j<len;j++){
            if(s[j]){
                int l=j+1,r=len,num=j;
                while(l<=r){
                    int mid=l+r>>1;
                    if(pre[get_hash(j+1,mid)]) num=mid,l=mid+1;
                    else r=mid-1;

                }   if(num>j&&num==len) Add[j+1].push_back(j),Del[num].push_back(j);
                bit.add(j,s[j]);
            }
        }
        int ans=0;
        for(int j=3;j<=len;j++){
            for(auto x:Add[j]) bit2.add(x,s[x]);
            if(j==len){
                int l=3,r=j,num=j+1;
                while(l<=r){
                    int mid=l+r>>1;
                    if(suf[get_hash(mid,j)]) num=mid,r=mid-1;
                    else l=mid+1;
                }
                ans+=bit2.sum(num-2),ans+=bit.sum(j-1)-bit.sum(num-2);
            }
            for(auto x:Del[j]) bit2.add(x,-s[x]);
            Add[j].clear();Del[j].clear();
        }cout<<ans<<'\n';
    }
    return 0;
}