「ALFR Round 5」E Another string problem 题解

wmrqwq · 2025-05-02 08:26:17 · 题解

验题人题解。

题目链接

「ALFR Round 5」E Another string problem

解题思路

考虑倍增。

注意到失配的次数显然不能大于 |T| - 1 次，否则一定不合法。

那么也就意味着一个 T 是合法的，当且仅当在 S 中最多只会有 |T| - 1 个断点。

暴力做法显然直接扫一遍原串暴力匹配过去即可。

我们考虑优化这个匹配的过程，若此时 T 匹配到了 L 这个位置，我们进行分讨：

• 若 L 为 T 的第一个位置，则我们可以直接倍增跳 T，特别的，若一个 T 都跳不了，则直接改为倍增跳 T 的字符，特别的，若一个字符都没有，则失配次数 + 1。

• 若 L 不为 T 的第一个位置，则我们可以直接倍增跳 T 的字符，特别的，若一个字符都没有，则失配次数 + 1。

显然每个位置最多只有一个倍增 \log |T| + \log |S| 的复杂度，总时间复杂度 O(\sum |S| \log |T| + |S| \log |S|)。

参考代码

string s,s2;
ll n,m,q;
ll hsh[200010][20];
ll nxt[20];
ll hashing[200010];
ll Pw[200010];
ll Base[]={131,223,233,666,10011},Mod[]={998244353,998244853,(ll)1e9+7,(ll)1e9+9};
ll base,mod;
ll B;
ll f(ll l,ll r){
    return (hashing[r]-hashing[l-1]*Pw[r-l+1]%mod+mod)%mod;
}
map<string,ll>mp;
void _clear(){}
void solve()
{
    mp.clear();
    base=Base[rand_lr(0,4)],mod=Mod[rand_lr(0,3)];
    Pw[0]=1;
    _clear();
    cin>>s>>q;
    n=s.size();
    B=1e18;
    s=' '+s;
    forl(i,1,n)
        Pw[i]=Pw[i-1]*base%mod;
    forl(i,1,n)
        hashing[i]=(hashing[i-1]*base+s[i])%mod;
    forl(i,1,q)
    {
        cin>>s2;
        m=s2.size();
        s2=' '+s2;
        if(mp[s2])
        {
            printat(mp[s2]==1);
            continue;
        }
        if(m>n)
        {
            aty;
            continue;
        }
        if(m>B)
        {
            ll sum=0,L=0;
            forl(j,1,n)
            {
                if(s2[L+1]==s[j])
                    L++;
                if(L==m)
                    L=0,
                    sum++;
            }
            printat(sum>=n/m);
            continue;
        }
        forl(i,1,m)
            hsh[i][0]=s2[i];
        forl(j,1,17)
            forl(i,1,m-pw(j)+1)
                hsh[i][j]=(hsh[i][j-1]*Pw[pw(j-1)]+hsh[i+pw(j-1)][j-1])%mod;
        ll num=0;
        forl(i,1,m)
            num=(num*base+s2[i])%mod;
        nxt[0]=num;
        forl(i,1,19)
            nxt[i]=(nxt[i-1]*Pw[min(pw(i-1)*m,200005ll)]%mod+nxt[i-1])%mod;

        ll sum=0,L=0,last=n%m;
        forl(i,1,n)
        {
            // cout<<i<<endl;
            if(last<0)
                break;
            if(L==0)
            {
                if(i+m-1>n)
                    break;
                if(f(i,i+m-1)!=nxt[0])
                {
                    if(s[i]!=s2[1])
                    {
                        last--;
                        continue;
                    }
                    forr(j,__lg(m),0)
                        if(L+1+pw(j)-1<=m && i+pw(j)-1<=n && hsh[L+1][j]==f(i,i+pw(j)-1))
                            i+=pw(j),
                            L+=pw(j),
                            sum+=L/m,
                            L%=m;
                    i--;
                    continue;
                }
                else
                {
                    forr(j,19,0)
                        if(i+pw(j)*m-1<=n && f(i,i+pw(j)*m-1)==nxt[j])
                            i+=pw(j)*m,
                            sum+=pw(j);
                    i--;
                    continue;
                }
            }
            else
            {
                if(s[i]!=s2[L+1])
                {
                    last--;
                    continue;
                }
                forr(j,__lg(m),0)
                    if(L+pw(j)-1<=m && i+pw(j)-1<=n && hsh[L+1][j]==f(i,i+pw(j)-1))
                        i+=pw(j),
                        L+=pw(j),
                        sum+=L/m,
                        L%=m;
                i--;
            }
        }
        // cout<<endl;
        // cout<<last<<' '<<sum<<endl;
        mp[s2]=(last>=0 && sum>=n/m)?1:-1;
        printat(last>=0 && sum>=n/m);
    }
}