题解：P3618 误会

题目链接

• 洛谷 P3618 误会

参考资料

• 前缀函数与 KMP 算法 - OI Wiki

题意简述

给定 $T$ 组数据，每组数据包含两个字符串 $A,B$。可以将字符串 $A$ 中与字符串 $B$ 相同的字串删去，问最终有多少种字符串 $A$ 可能的结果？

解题思路

看到字符串匹配首先想到 KMP 算法。

因为某一个字符串是否替换只影响与之相交的字符串（无后效性），所以考虑 DP。

设 $f_i$ 表示前 $i$ 位的替换方案数，$p$ 为当前已匹配到的 $B$ 字符串位数，则：

$$f_i=\begin{cases} f_{i-1} & p\not=m \\ f_{i-1}+f_{i-m} & p=m \end{cases}$$

于是就有了一个朴素的 KMP 混合 DP 的算法，时间复杂度为 $O(T(|A| +|B|))$，甚至拿到了最优解 rk3。

参考代码（附注释）

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

const long long N = 100005 , mod = 1e9+7;
long long T , n , m , p , nxt[N] , f[N];
string a , b;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> T;
    f[0] = 1;//最开始只有一种方案
    for(long long k = 1 ; k <= T ; k++)
    {
        cin >> a >> b;
        n = a.size();
        a = '#' + a;
        m = b.size();
        b = '#' + b;
        p = 0;
        for(long long i = 2 ; i <= m ; i++)//预处理
        {
            while(b[i] != b[p + 1] && p)
            {
                p = nxt[p];
            }
            if(b[i] == b[p + 1])
            {
                p++;
            }
            nxt[i] = p;
        }
        p = 0;
        for(long long i = 1 ; i <= n ; i++)//kmp加dp
        {
            while(b[p + 1] != a[i] && p)
            {
                p = nxt[p];
            }
            if(b[p + 1] == a[i])
            {
                p++;
            }
            f[i] = f[i - 1];
            if(p == m)
            {
                f[i] = (f[i] + f[i - m]) % mod;//dp转移
            }
        }
        cout << "Case #" << k << ": " << f[n] << endl;//别忘记输出格式
    }
    //system("pause");
    return 0;
}