题解：P3618 误会

· · 题解

参考资料

题意简述

给定 T 组数据，每组包含一个长度为 n 的字符串 s 和一个长度为 m 的字符串 t。

可以将 s 中任意与 t 相同的子串替换为 *，求有多少种不同的替换方案。

解题思路

定义 f_i 表示在 s[0:i] 范围内进行替换的方案数，分类讨论：

  1. 当 i<m 时，字符串长度不足，无法替换，所以 f_i=1。
  2. 若 s[i-m:i-1]=t，可以选择替换 s[i-m:i-1]，但要求替换前的部分不能重叠。因此可以增加方案数 f_{i-m}，所以 f_i\gets f_{i-1}+f_{i-m}。
  3. 否则，只能选择不替换，所以 f_i\gets f_{i-1}。

列出状态转移方程：

f_i= \begin{cases} 1 & i<m \\ f_{i-1}+f_{i-m} & s[i-m:i-1]=t \\ f_{i-1} & \text{otherwise} \end{cases}

利用 KMP 算法 或 Rabin–Karp 算法（Hash）等字符串匹配算法，可以单次 O(1) 判断 s[i-m:i-1]=t 是否成立。

参考代码

KMP 算法

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
const int N=100005;
int nxt[N],f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int $=1;$<=T;$++)
    {
        string s,t;
        cin>>s>>t;
        int n=s.size(),m=t.size();
        for(int i=1;i<m;i++)
        {
            int j=nxt[i-1];
            while(j&&t[i]!=t[j])j=nxt[j-1];
            if(t[i]==t[j])j++;
            nxt[i]=j;
        }
        f[0]=1;
        for(int i=0,j=0;i<n;i++)
        {
            while(j&&s[i]!=t[j])j=nxt[j-1];
            if(s[i]==t[j])j++;
            f[i+1]=i<m?1:f[i]%mod;
            if(j==m)f[i+1]=(f[i+1]+f[i-m+1])%mod;
        }
        cout<<"Case #"<<$<<": "<<f[n]<<'\n';
    }
    return 0;
}

Rabin–Karp 算法

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int base=131;
const int mod=1e9+7;
const int N=100005;
ull Pow(ull a,ull b)
{
    ull res=1;
    while(b)
    {
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int f[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    for(int $=1;$<=T;$++)
    {
        string s,t;
        cin>>s>>t;
        int n=s.size(),m=t.size();
        ull h1=0,h2=0,p=Pow(base,m-1);
        for(int i=0;i<m;i++)
        {
            f[i]=1;
            h1=h1*base+s[i];
            h2=h2*base+t[i];
        }
        s+='$';
        for(int i=m;i<=n;i++)
        {
            f[i]=f[i-1]%mod;
            if(h1==h2)f[i]=(f[i]+f[i-m])%mod;
            h1=(h1-s[i-m]*p)*base+s[i];
        }
        cout<<"Case #"<<$<<": "<<f[n]<<'\n';
    }
    return 0;
}