XCPC wiki - 字符串 02 - 字符串哈希

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ulll = __uint128_t;

constexpr int N = 1e6 + 8;
constexpr ull mod = (1ull << 61) - 1;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ull> dist(mod / 2, mod - 1);
const ull H = dist(rnd);

struct mull {
    ull x;
    constexpr mull(ull x = 0) : x{ norm(x) } {}
    constexpr ull norm(ull x) const { return x >= mod ? x - mod : x; }
    friend constexpr mull operator*(mull a, mull b) { return ulll(a.x) * b.x % mod; }
    friend constexpr mull operator+(mull a, mull b) { return a.norm(a.x + b.x); }
    friend constexpr mull operator-(mull a, mull b) { return a.norm(a.x + mod - b.x); }
    friend constexpr bool operator==(mull a, mull b) { return a.x == b.x; }
    friend constexpr bool operator!=(mull a, mull b) { return a.x != b.x; }
} power[N];

struct Hash {
    string s;
    vector<mull> h;
    Hash() {
        cin >> s;
        init(s);
    }
    Hash(const string& s) : s(s) {
        init(s);
    }
    void init(const string& s) {
        const int n = s.size();
        h.resize(n + 1);
        for (int i = 0; i < n; i++) {
            h[i + 1] = h[i] * H + s[i];
        }
    }
    mull operator()(int l, int r) {
        return h[r] - h[l] * power[r - l];
    }
    auto size() {
        return s.size();
    }
};

void beforeT() {
    power[0] = 1;
    for (int i = 1; i < N; i++) {
        power[i] = power[i - 1] * H;
    }
}

BUC3399K - 下笔成章

给定字符串$s$，求最长长度的子串$t$，满足$t$ 既是$s$ 的前缀，又是$s$ 的后缀，同时在字符串中还出现过一次（在除前后缀以外出现，可能和前后缀有部分重合）。不存在则输出 I'll write one for you。

数据范围：$|s|\in[1,1e6]$。

Input	Output
fixprefixixffix	fix

Hash s;
const int n = s.length();
for (int j = n; j >= 1; --j) {
    if (s(0, j) != s(n - j, n)) continue;
    for (int i = 1; i < n - j; ++i) {
        if (s(0, j) == s(i, i + j)) {
            cout << s.s.substr(0, j) << '\n';
            return 0;
        }
    }
}
cout << "I'll write one for you\n";

BUC3399N - 赞美太阳

将$A$ 的首字母移到末尾，执行任意次，可以得到所有和$A$ 结构相同的字符串。$n$ 次询问，每次给出一个字符串，问有多少个子串和$A$ 结构相同。

数据范围：$\sum|s|\in[1,1e7]$。

Input	Output
abab 2 abababab ababcbaba	5 2

string s;
cin >> s;
Hash ss(s + s);
map<ull, int> mp;
for (int i = 0; i < s.length(); ++i) {
    mp[ss(i, i + s.length()).x] = 1;
}
int t;
cin >> t;
while (t--) {
    Hash t;
    int ans = 0;
    for (int l = 0; l + s.length() <= t.length(); ++l) {
        ans += mp.count(t(l, l + s.length()).x);
    }
    cout << ans << '\n';
}

2024 杭电多校 1001 - 循环位移

[[…/contests/2024 杭电多校 /2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）|2024-07-19：2024“钉耙编程”中国大学生算法设计超级联赛（1）]]

定义字符串$S=S_0+\dots+S_{n-1}$ 循环位移$k$ 次为$S(k)$，[A] = \set{A(k), k \in \mathbb N}。给出$T$ 组串$A, B$，询问$B$ 有多少个子串在$[A]$ 中。

（代码同上）

VJspr11H - 相似基因序列问题

题意 给定 $n$ 个长度为 $m$ 的字符串 $s_1, \dots,s_N$。定义两个字符串相似：最多只有 $k$ 个对应字母不同。$q$ 组询问，每次给出一个长度为 $m$ 的字符串，问与几个$s_{i}$ 相似。数据范围：$1 \leqslant n, q \leqslant 300$，$1 \leqslant m \leqslant 60,000$，$1 \leqslant K \leqslant 10$。

思路 突破口是$k$ 很小，也就是说字符串大部分是相同的，用倍增 / 二分跳到下一个不相同的位置。$n,q$ 也很小，所以两两匹配就行。时间复杂度$\Theta(qnk\log m)$。

int n, q, m, k;
cin >> n >> q >> m >> k;
vector<Hash> s(n);
while (q--) {
    Hash t;
    int res = 0;
    for (int id = 0; id < n; ++id) {
        int kcnt = 0, i = 0;
        while (i < m) {  // 比较第 i 位是否相同
            if (t(i, i + 1) != s[id](i, i + 1)) {
                if (++kcnt > k) break;
            }
            int len = m - i;
            while (len) {
                if (t(i, i + len) != s[id](i, i + len)) len /= 2;
                else break;
            }
            i += max(1, len);
        }
        res += kcnt <= k;
    }
    cout << res << endl;
}

2024 杭电多校 10009 - 不基本子串结构

[[…/contests/2024 杭电多校 /2024-08-18：2024“钉耙编程”中国大学生算法设计超级联赛（10）|2024-08-18：2024“钉耙编程”中国大学生算法设计超级联赛（10）]]

Hash s, t;
if (s.length() < t.length()) {
    swap(s, t); // 保证 s 是长串 t 是短串 
}
// Hash 匹配字符串
int cnt = 0;  // 匹配成功的数量
for (int i = 0; i + t.length() <= s.length(); ++i) {
    cnt += s(i, i + t.length()) == t(0, t.length());
}
int res;
if (cnt > 1) {
    res = -1;
}
else if (cnt == 1) {
    res = s.length();
}
else {
    // 找最长的 s[0] 的前缀和 s[1]的后缀
    int mx = 0;
    for (int i = 1; i <= t.length(); ++i) {
        if (s(0, i) == t(t.length() - i, t.length()) ||
            t(0, i) == s(s.length() - i, s.length())) {
            mx = max(mx, i);
        }
    }
    res = s.length() + t.length() - mx;
}
cout << res << '\n';