题解：P14363 [CSP-S 2025] 谐音替换 / replace

· · 题解

闲话

挑战最短代码！

Solution

观察到题目嵌定了 \sum_{i=1}^{n} |S_{i,1}|+|S_{i,2}| \le 5 \times 10^{6} 所以我们能发现 S 的长度只会有 \sqrt{5 \times 10^{6}} 种，所以我们考虑枚举长度，使用哈希判断前后是否相等即可，最好理解的一集！

所以我们每一次枚举一个位置 i 表示，从 t_{j,0} 的第 i 个位置开始进行匹配，在枚举匹配串的长度，前面证明过了，只有根号级别，假设为 v 则我们需要判断 t_{j,0} 的 [i,i+v-1] 被替换后是否能变成 t_{j,1} 这个所有的步骤都可以使用哈希进行判断。

目前通过了民间数据最慢的点 298ms。

更新：

通过了官方数据，洛谷上最慢的点是 1.42s。

这里补一个较为严谨证明的复杂度，虽然极限复杂度仍然会超时，首先我们容易得到复杂度最极限的时候是 \mathcal{O}(L2 \sqrt{L1}) 的，但是观察到保证 |S_{i,1}|=|S_{i,2}| 和 |t_{j,1}|=|t_{j,2}| 所以说我们每一次枚举的时候其实仅有 \frac{L2}{2} 个字符被枚举到了，同理 L1 也是，所以这个代码带 \frac{1}{4} 的常数，算出来只有 2.7 \times 10^{9} 应该是比较快了。

Code

//Author:Kevin Z K Y
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define fst first
#define sed second
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<0)?(-(x)):(x))
using namespace std;
using us = unsigned short ;using ldb = long double ;
using ull = unsigned long long ;using ui = unsigned int ;
using ll = long long ;using hint = __int128 ;
using pii = pair<int,int> ;using pll = pair<ll,ll> ;
using pil = pair<int,ll> ;using vpil = vector<pil> ;
using pli = pair<ll,int> ;using vpli = vector<pli> ;
using vi = vector<int> ;using vl = vector<ll> ;
using vpi = vector<pii> ;using vpl = vector<pll> ;
using db = double ;namespace mystl{
    #define gc() getchar()
    inline ll qpow(ll a , ll b , ll p) { if (a==0ll) return 0ll; ll c=1ll;
              while(b) { if(b & 1) c=a*c%p; a=a*a%p; b>>=1; } return c ; }
    void exgcd ( ll a , ll b , ll & cx , ll & cy){if(a % b==0)cx = 0,cy=1;
                else { exgcd( b , a % b , cy , cx) ; cy -= a / b * cx ; }}
    inline ll lcm ( ll x , ll y ){return x / std :: __gcd( x , y ) * y ; }
    template<typename T>inline void read(T&x) {x=0; bool f=false; char ch;
                ch = gc(); while(ch<'0'||ch>'9') f |=( ch=='-') , ch=gc();
                while(ch>='0'&&ch<='9') x=x*10+ch-'0', ch=gc(); x=f?-x:x;}
    template<typename T>inline void write(T x){char s[40];short d=0;T y=x;
                if(x<0) putchar('-'),y=-y;if(x==0){ putchar('0'); return;}
                while(y){s[++d]=y%10+48;y/=10;}while(d>0)putchar(s[d--]);}
    template<typename T>inline void wris(T x,char c){write(x);putchar(c);}
}using namespace mystl;
namespace my{
    const int N=(int)(2e5+5),W=(int)(5e6+5),SL=2250;
    const ull base=131;
    string s[N][2];
    int lenf[N],n,q;
    vi gotlen;
    int boxlen[W],idx[W];
    ull hashs[W][2];
    map<pair<ull,ull>,int>mp[SL];
    ull pre[W],pres[W],suf[W],sufs[W],pw[W];
    ull querya(int l,int r){
        return pre[r]-pre[l-1]*pw[r-l+1];
    }
    ull queryb(int l,int r){
        return pres[r]-pres[l-1]*pw[r-l+1];
    }
    inline void SOLVE(){
        cin>>n>>q;
        up(i,1,n)cin>>s[i][0]>>s[i][1],lenf[i]=(int)s[i][0].length(),
            boxlen[lenf[i]]++;
        pw[0]=1;
        up(i,1,W){
            pw[i]=pw[i-1]*base;
            if(boxlen[i])gotlen.push_back(i);
        }
        reverse(gotlen.begin(),gotlen.end());
        int lenlen=(int)gotlen.size();
        up(i,0,lenlen-1)idx[gotlen[i]]=i+1;
        up(i,1,n){
            up(j,0,lenf[i]-1)
                hashs[i][0]=hashs[i][0]*base+s[i][0][j],
                hashs[i][1]=hashs[i][1]*base+s[i][1][j];
            mp[idx[lenf[i]]][{hashs[i][0],hashs[i][1]}]++;
//          cout<<hashs[i][0]<<' '<<hashs[i][1]<<'\n';
        }
        while(q--){
            string a,b;cin>>a>>b;
            int len=(int)a.length();
            a=" "+a;b=" "+b;
            pre[0]=pres[0]=suf[len+1]=sufs[len+1]=0;
            up(i,1,len)
                pre[i]=pre[i-1]*base+a[i],
                pres[i]=pres[i-1]*base+b[i];
            dn(i,len,1)
                suf[i]=suf[i+1]*base+a[i],
                sufs[i]=sufs[i+1]*base+b[i];
//          up(i,1,len)cout<<pre[i]<<" \n"[i==len];
//          up(i,1,len)cout<<pres[i]<<" \n"[i==len];
//          up(i,1,len)cout<<suf[i]<<" \n"[i==len];
//          up(i,1,len)cout<<sufs[i]<<" \n"[i==len];
            ll ans=0;
            up(i,1,len){
                if(pre[i-1]!=pres[i-1])break;
                for(int v:gotlen){
                    if(i+v-1>len)continue;
                    if(suf[i+v]!=sufs[i+v])break;
//                  cout<<"isin\n";
                    ull hasha=querya(i,i+v-1),hashb=queryb(i,i+v-1);
                    if(mp[idx[v]].find({hasha,hashb})!=mp[idx[v]].end())
                        ans+=mp[idx[v]][{hasha,hashb}];
//                  cout<<i<<' '<<v<<' '<<hasha<<' '<<hashb<<' '<<ans<<'\n';
                }
            }
            cout<<ans<<'\n';
        }
    }
}
int main(){
//  freopen("s.in","r",stdin);
//  freopen("my.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int _=1;while(_--)my::SOLVE();return 0;
}
/*

*/