P10992 Solution

Description

Link

Solution

好题。

本题主要有两个问题：哈希函数的设计和子串的枚举。

作为哈希题的套路，首先可以想到二分答案长度，再做 check。

考虑如何设计哈希函数来 check。令二分出的长度为 \(len\)。

设计出的哈希函数需要满足两个条件：两个串对应的字符集相同，对应字符集的下标相同。默认字符集可重。

考虑以下哈希函数：

令 \(g(i)\) 为表示从 \(i\) 到 \(i + len - 1\) 这一段字符串的所有字母的哈希值，具体怎么设计待会再说。

令 \(h(i)\) 表示从 \(i\) 到 \(i + len - 1\) 这一段字符串 \(g(i)\) 的哈希值，即 \(\begin{aligned} h(i) = \bigoplus^{i+len-1}_{j=1} g(j)\end{aligned}\)。

对于两个字符串，分别求解哈希值，对于每个第一个字符串的哈希值，只需要找到第二个字符串的哈希值就可以了。这部分可以对第二个字符串的哈希值排序，然后二分，枚举子串的问题就解决了。

接下来，思考一个问题：哈希函数 \(g(i)\)。

可以考虑一个类似于滑动窗口的转移：对于当前字符串的子串 \([i, i + len - 1]\)，对于每一个下标赋一个权值 \(w_j\)，即对于每一个 \(j = [i, i + len - 1]\)，\(w_j=j-i+1\)。

比如说字符串 aba，对于字符 a，其权值为 \(base^1+base^3\)；对于字符 b，其权值为 \(base^2\)。

Code

// PikachuQAQ 2024/10/18

#include <bits/stdc++.h>

using namespace std;
using ull = unsigned long long;

const int kN = 1e5 + 2, base = 137;

int n, m, mx, mi, ans;
string s, t;
ull has1[kN], has2[kN], bpow[kN], cnt[30];

void solve(string s, int l, int r) {
    fill(cnt, cnt + 30, 0);
    for (int i = l; i <= r; i++) {
        cnt[s[i] - 'a'] += bpow[i - l + 1];
    }
}

void solve_hash(int l) {
    has1[l] = 0;
    for (int i = 0; i < 26; i++) {
        has1[l] ^= cnt[i];
    }
}

bool check(int len) {
    solve(t, m - len + 1, m), solve_hash(m - len + 1);
    for (int l = m - len, r = m - 1; l >= 1; l--, r--) {
        cnt[t[r + 1] - 'a'] -= bpow[len];
        for (int i = 0; i < 26; i++) cnt[i] *= base;
        cnt[t[l] - 'a'] += base;
        solve_hash(l);
    }
    for (int i = 1; i <= m - len + 1; i++) {
        has2[i] = has1[i];
    }
    solve(s, n - len + 1, n), solve_hash(n - len + 1);
    for (int l = n - len, r = n - 1; l >= 1; l--, r--) {
        cnt[s[r + 1] - 'a'] -= bpow[len];
        for (int i = 0; i < 26; i++) cnt[i] *= base;
        cnt[s[l] - 'a'] += base;
        solve_hash(l);
    }
    sort(has2 + 1, has2 + m - len + 2);
    for (int i = 1, res; i <= n - len + 1; i++) {
        if (binary_search(has2 + 1, has2 + m - len + 2, has1[i])) return 1;
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s >> t;
    n = s.size(), m = t.size(), mx = max(n, m), mi = min(n, m);
    s = " " + s, t = " " + t;
    bpow[0] = 1;
    for (int i = 1; i <= mx; i++) {
        bpow[i] = bpow[i - 1] * base;
    }
    for (int l = 1, r = mi, mid; l <= r; ) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            l = mid + 1, ans = mid;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;

    return 0;
}