备战2024XCPC--字符串做题笔记

TJUHuangTao / 2024-09-25 / 原文

前言

应该是算竞生涯的最后两、三个月了，现在打算直接all in字符串，看看到时候能不能碰上个开的出来的字符串题，下面是一些做题的题的记录和经验总结。

CF963D

题目大概是给一个字符串S，又有很多询问，给k 和 T，要找S最小的区间，使得区间内包含k个T。
在评论区学到了一种用bitset来维护字符串的endpose集合的方法，在数据范围不是特别大的时候可以用,而且可以使用bitset的_Find_first() 以及 _Find_next(x)函数，可以用来遍历bitset的所有1的位置。
复杂度 $O(\frac{|S|\times \sum |T|}{w})$

点击查看代码

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
bitset<maxn> bs[26], cur;
void solve() {
    string str; cin >> str;
    int n = str.length();
    for (int i = 1; i <= n; i++)
        bs[str[i - 1] - 'a'][i] = 1;
    int q; cin >> q;
    while (q--) {
        cur.set();
        int k; cin >> k;
        string s; cin >> s;
        int m = s.length();
        for (int j = 1; j <= m; j++) {
            cur &= (bs[s[j - 1] - 'a'] << (m - j));
        }
        if (cur.count() < k) {
            cout << -1 << "\n";
            continue;
        }
        vector<int> vec;
        for (auto it = cur._Find_first(); it != maxn; it = cur._Find_next(it))
            vec.push_back(it);
        int ans = inf;
        for (int i = k - 1; i < vec.size(); i++)
            ans = min(ans, vec[i] - vec[i - k + 1] + m);
        cout << ans << "\n";
    }
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

CF914F

和刚刚那题差不多，要求带修的字符串，查询区间内，某个字符串出现次数，也是可以用bitset维护一下就好。不过区别在于这题不能暴力遍历1的位置，得直接用移位加count()来统计。
刚刚看了下证明，因为上一题有保证所有查询字符串互不相同，所以endpos大小和是 $n \sqrt(n)$ ，这题没有保证这个，所以暴力遍历1会超时。

点击查看代码

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 998244353;
bitset<maxn> bs[26], cur;
void solve() {
    string str; cin >> str;
    int n = str.length();
    for (int i = 1; i <= n; i++)
        bs[str[i - 1] - 'a'][i] = 1;
    int q; cin >> q;
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int pos; char ch;
            cin >> pos >> ch;
            bs[str[pos - 1] - 'a'][pos] = 0;
            str[pos - 1] = ch;
            bs[str[pos - 1] - 'a'][pos] = 1;
        } else {
            int l, r; string s;
            cin >> l >> r >> s;
            cur.set();
            int m = s.length();
            for (int j = 1; j <= m; j++)
                cur &= bs[s[j - 1] - 'a'] << (m - j);
            int ans = (cur >> (l + m - 1)).count() - (cur >> (r + 1)).count();
            cout << max(0, ans) << "\n";
        }
    }
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}