tomorin的字符串迷茫值

题目描述

tomorin定义一个字符串的迷茫值为该字符串包含"mygo"连续子串的个数。例如"mygomygo"、"itsmygo"的迷茫值分别为 2，1，而"bangdream"的迷茫值为 0。

现在tomorin有一个字符串，她准备删除一些字符，但不能删除两个连续字符。

tomorin想知道在所有删除方案中，字符串的迷茫值之和是多少？

由于答案可能很大，你需要将答案对 $10^9+7$ 取模。

输入描述:

一个仅包含小写字母的字符串，长度不超过 $2 \times 10^5$。

输出描述:

一个整数，代表迷茫值之和。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果。

示例1

输入

mygogo

输出

3

说明

方案 1：什么都不删，"mygogo"，迷茫值为 1。

方案 2：删除第 5 个字符，"mygoo"，迷茫值为 1。

方案 3：删除第 6 个字符，"mygog"，迷茫值为 1。

因此答案为 3。

解题思路

  感觉是用贡献法的一类题。只要遇到统计某些量的题目时，可以考虑答案是由哪些情况做出贡献的，然后再去枚举这些情况分别统计。

  显然在这题中只有在删除后是 "mygo" 的子串才会对答案有贡献，那么就可以按照左端点将子串进行分类，枚举看看以 $i$ 为左端点的子串有多少种删除操作变成 "mygo"。由于在删除操作中不能删除两个相邻的字符，因此如果两个字符的距离超过 $2$，那么这两个字符间的字符不可能被删完。因此如果要获得 "mygo"，那么只有这 $2^3 = 8$ 种子串可以得到："mygo"，"m_ygo"，"my_go"，"myg_o"，"m_y_go"，"m_yg_o"，"my_g_o"，"m_y_g_o"。其中 "_" 指任意一个字符。

  只需依次枚举这 $8$ 种子串，看看是否匹配以 $i$ 为左端点的子串。子串内的删除方法是固定的，子串的两边即 $[1,i-1]$ 和 $[i+m,n]$（$m$ 指 $8$ 种子串的长度）的方法是任意的，可以用动态规划来预处理。

  定义 $f(i,0)$ 表示区间 $[1,i]$ 中不删除第 $i$ 个字符的所有删除方法的数量。同理 $f(i,1)$ 表示区间 $[1,i]$ 中删除第 $i$ 个字符的所有删除方法的数量。状态转移方程就是 $f(i,0) = f(i-1,0) + f(i-1,1)$，$f(i,1) = f(i-1,0)$。那么区间 $[1,i]$ 的所有删除方案就是 $f(i,0)+f(i,1)$。同理定义 $g(i,0)$ 表示区间 $[i,n]$ 中不删除第 $i$ 个字符的所有删除方法的数量，$g(i,1)$ 表示区间 $[i,n]$ 中删除第 $i$ 个字符的所有删除方法的数量。状态转移方程就是 $g(i,0) = g(i+1,0) + g(i+1,1)$，$g(i,1) = g(i+1,0)$。那么区间 $[i,n]$ 的所有删除方案就是 $g(i,0)+g(i,1)$。

  因此以 $i$ 为左端点的子串如果匹配这 $8$ 种子串的某一个，其对答案的贡献就是 $\left(f(i-1,0) + f(i-1,1)) \cdot (g(i+m,0) + g(i+m,1)\right)$。

  AC 代码如下，时间复杂度为 $O(n)$：

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

const int N = 2e5 + 10, mod = 1e9 + 7;

int f[N][2], g[N][2];

int main() {
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
        f[i][1] = f[i - 1][0];
    }
    g[n + 1][0] = 1;
    for (int i = n; i; i--) {
        g[i][0] = (g[i + 1][0] + g[i + 1][1]) % mod;
        g[i][1] = g[i + 1][0];
    }
    int ret = 0;
    vector<string> p({"mygo", "m_ygo", "my_go", "myg_o", "m_y_go", "my_g_o", "m_yg_o", "m_y_g_o"});
    for (int i = 1; i <= n; i++) {
        for (auto &t : p) {
            int m = t.size();
            if (i + m - 1 > n) continue;
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (t[j] == '_') continue;
                if (s[i + j] != t[j]) flag = false;
            }
            if (flag) ret = (ret + 1ll * (f[i - 1][0] + f[i - 1][1]) * (g[i + m][0] + g[i + m][1])) % mod;
        }
    }
    cout << ret;
    
    return 0;
}

参考资料

  出题人题解：https://ac.nowcoder.com/discuss/1252622