题解 | #不是烤串故事#

字符串哈希快速判断两个字符串是否相等

假设最长公共前缀的函数是, 那么随着增大一定是非递减, 也就是具有二分性质

字符串哈希模板

struct Hash {
    vector<LL> h, p;
    const LL B = 131;
    Hash (const string &s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            p[i] = p[i - 1] * B % MOD;
            h[i] = (h[i - 1] * B % MOD + s[i - 1]) % MOD;
        }
    }

    LL get_hash(int l, int r) {
        LL v = (h[r] - h[l - 1] * p[r - l + 1] % MOD) % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

代码

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 1e9 + 7;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

struct Hash {
    vector<LL> h, p;
    const LL B = 131;
    Hash (const string &s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 1; i <= n; ++i) {
            p[i] = p[i - 1] * B % MOD;
            h[i] = (h[i - 1] * B % MOD + s[i - 1]) % MOD;
        }
    }

    LL get_hash(int l, int r) {
        LL v = (h[r] - h[l - 1] * p[r - l + 1] % MOD) % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    string rev = s;
    reverse(all(rev));

    Hash a(s), b(t), c(rev);
    auto check = [&](int mid, int k) {
        if (mid > n) return 0;
        int ok = 0;
        if (mid <= k) {
            if (c.get_hash(n - k + 1, n - k + mid) == b.get_hash(1, mid)) ok = 1;
        }
        else {
            if (c.get_hash(n - k + 1, n) == b.get_hash(1, k)) {
                if (a.get_hash(k + 1, mid) == b.get_hash(k + 1, mid)) ok = 1;
            }
        }
        return ok;
    };

    int maxv = 0, idx = 1;
    for (int i = 1; i <= n; ++i) {
        int l = 0, r = n, cur = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            if (mid == 0) {
                l = mid + 1;
                continue;
            }
            if (check(mid, i)) {
                cur = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        if (cur > maxv) {
            maxv = cur;
            idx = i;
        }
    }

    cout << maxv << ' ' << idx << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}