题目分析

题目要求统计满足条件的不同字符串T的数量，其中T是S的子串且存在一个出现位置对应的子串是“好的”（坏字母数量不超过k）。核心思路是先找到所有“好的”子串区间，再统计这些区间内包含的不同子串数量，避免重复计数。

解题思路

1. 滑动窗口找好区间：通过滑动窗口预处理每个起始位置i对应的最远结束位置r[i]，使得子串S[i..r[i]-1]是好的（坏字母数≤k）。
2. 后缀数组去重：使用后缀数组（SA）处理字符串S，利用后缀数组的性质（排名相邻的后缀最长公共前缀LCP）来统计不同子串。具体来说，对于每个后缀起始位置j，其能贡献的新子串数量为好区间长度减去与前一个后缀的LCP长度，从而避免重复计数。

代码实现

#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

struct SA {
    int n;
    std::vector<int> sa, rk, lc;
    SA(std::string s) {
        n = s.size();
        sa.resize(n);
        lc.resize(n - 1);
        rk.resize(n);
        std::iota(sa.begin(), sa.end(), 0);
        std::sort(sa.begin(), sa.end(),
        [&](int a, int b) {
            return s[a] < s[b];
        });
        rk[sa[0]] = 0;

        for (int i = 1; i < n; i++) {
            rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        }

        int k = 1;
        std::vector<int> tmp, cnt(n);
        tmp.reserve(n);

        while (rk[sa[n - 1]] < n - 1) {
            tmp.clear();

            for (int i = 0; i < k; i++) {
                tmp.push_back(n - k + i);
            }

            for (auto i : sa) {
                if (i >= k) {
                    tmp.push_back(i - k);
                }
            }

            std::fill(cnt.begin(), cnt.end(), 0);

            for (int i = 0; i < n; i++) {
                cnt[rk[i]]++;
            }

            for (int i = 1; i < n; i++) {
                cnt[i] += cnt[i - 1];
            }

            for (int i = n - 1; i >= 0; i--) {
                sa[--cnt[rk[tmp[i]]]] = tmp[i];
            }

            std::swap(rk, tmp);
            rk[sa[0]] = 0;

            for (int i = 1; i < n; i++) {
                rk[sa[i]] =
                    rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] ||
                                     sa[i - 1] + k == n ||
                                     tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
            }

            k *= 2;
        }

        for (int i = 0, j = 0; i < n; i++) {
            if (rk[i] == 0) {
                j = 0;
            } else {
                for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n &&
                        s[i + j] == s[sa[rk[i] - 1] + j];) {
                    j++;
                }

                lc[rk[i] - 1] = j;
            }
        }
    }
};

void solve() {
    string s, t;
    int k;
    cin >> s >> t >> k;

    for (auto &k : t)
        k = '1' + '0' - k;

    vector<int> r(s.size());

    for (int i = 0, j = 0, sum = 0; i < s.size(); i++) {
        while (j < s.size() && sum + t[j] - '0' <= k)
            sum += t[j] - '0', j++;

        r[i] = j;
        sum -= t[i] - '0';
    }

    SA sa(s);
    int pre = 0;
    ll res = 0;

    for (int i = 0; i < s.size(); i++) {
        int j = sa.sa[i];
        int cur = r[j] - j;

        if (i)
            pre = min(pre, sa.lc[i - 1]);

        if (cur > pre)
            res += cur - pre, pre = cur;
    }

    cout << res << '\n';
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;

    while (t--)
        solve();

    return 0;
}

代码解释

1. 后缀数组构造（SA结构体）：

   • 初始化后缀数组sa，按首字符排序得到初始排名。
   • 通过倍增法排序后缀，逐步比较长度为2^k的子串，更新sa和排名rk。
   • 计算相邻后缀的最长公共前缀lc数组。

2. 滑动窗口预处理：

   • 将坏字母标记转换为数值（坏字母为1，好字母为0）。
   • 滑动窗口找到每个起始位置i的最远结束位置r[i]，确保子串S[i..r[i]-1]的坏字母数≤k。

3. 统计不同子串：

   • 遍历后缀数组中的每个后缀起始位置j，计算其好区间长度cur = r[j] - j。
   • 利用lc数组获取当前后缀与前一个后缀的LCP长度，避免重复统计相同子串，累加有效新子串数量。