题解：P3785 [SDOI2017] 文本校正

· · 题解

假如说咱不会任何字符串算法呢？

哈希！哈！

考虑分讨切成的三段 ABC 的排列顺序：

  1. ABC：原串。
  2. ACB：前缀相等，后缀循环轮换。
  3. BAC：后缀相等，前缀循环轮换。
  4. BCA：整串循环轮换。
  5. CAB：整串循环轮换。
  6. CBA：后缀匹配前缀，剩下的循环轮换。

只要我们能做到快速判断一个串是否和另一个串循环同构即可。

循环同构哈希展现神力！

具体地说，相似矩阵的迹相等，即 \text{tr}(AB)=\text{tr}(BA)，并且连乘内部任意交换通常不相等，这就是我们想要的性质啦。

所以对每个字符随机一个矩阵，查询时获取区间乘积，判断迹是否相等即可。

同时你惊讶发现这里只需要查询前后缀乘积，非常舒服。

注意为了保证正确性，至少需要 3\times3 的矩阵，不然来个反着的直接爆了。

常数也太大了吧？？

别写双哈希了。可以使用 2^{61}-1 做模数，这就很牛了，取模可以直接位运算做，然后可以封装一个函数 _l(a, b, c) 表示 a+bc 取模的值，用的很爽。

同时可以让每个字符的矩阵都是 \begin{bmatrix}0&1&x_c\\0&0&1\\1&y_c&0\end{bmatrix} 的样子，这样行列式恒为 1，并且乘一次只需要 6 次乘法，查询子串也只需要 9 次乘法，真的是太神奇了。

这个东西还有一些很牛的用途。先藏一下。

时间复杂度 \mathcal O(n)，代码就很好写了。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef unsigned long long ll; typedef __uint128_t lll;
const int N = 1e6 + 5; const ll P = (1ull << 61) - 1, B = 13333331;
int T, n, m, s[N], t[N]; ll X[N], Y[N], pw[N], hs[N], ht[N], pres[N], sufs[N], pret[N], suft[N];
il ll _a(ll a, ll b) { return (a += b) >= P ? a - P : a; }
il ll _d(ll a, ll b) { return a >= b ? a - b : a + P - b; }
il ll _p(ll a, ll b) { lll t = (lll)a * b; return (t = (t >> 61) + (t & P)) >= P ? t - P : t; }
il ll _l(ll a, ll b, ll c) { lll t = (lll)b * c + a; return (t = (t >> 61) + (t & P)) >= P ? t - P : t; }
il ll Hash(ll h[], int l, int r) { return _d(h[r], _p(h[l - 1], pw[r - l + 1])); }
void calc(int s[], ll pre[], ll suf[]) {
    ll A[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
    for (int i = 1; i <= n; i++) {
        ll x = X[s[i]], y = Y[s[i]];
        for (int j = 0; j < 3; j++) {
            ll a = A[j][0], b = A[j][1], c = A[j][2];
            A[j][0] = c, A[j][1] = _l(a, c, y), A[j][2] = _l(b, a, x);
        }
        pre[i] = _a(A[0][0], _a(A[1][1], A[2][2]));
    }
    memset(A, 0, sizeof(A)), A[0][0] = A[1][1] = A[2][2] = 1;
    for (int i = n; i; i--) {
        ll x = X[s[i]], y = Y[s[i]];
        for (int j = 0; j < 3; j++) {
            ll a = A[0][j], b = A[1][j], c = A[2][j];
            A[0][j] = _l(b, c, x), A[1][j] = c, A[2][j] = _l(a, b, y);
        }
        suf[i] = _a(A[0][0], _a(A[1][1], A[2][2]));
    }
}
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) cin >> t[i];
    for (int i = 1; i <= n; i++) hs[i] = _l(s[i], hs[i - 1], B), ht[i] = _l(t[i], ht[i - 1], B);
    if (hs[n] == ht[n]) return void(cout << "YES\n1 1\n2 2\n3 " << n << '\n');
    for (int i = 1; i < n; i++)
        if (Hash(ht, i + 1, n) == Hash(hs, 1, n - i) && Hash(ht, 1, i) == Hash(hs, n - i + 1, n)) {
            cout << "YES\n";
            if (i > 1) cout << i + 1 << ' ' << n << "\n1 1\n2 " << i << '\n';
            else cout << "2 2\n3 " << n << "\n1 1\n"; return;
        }
    calc(s, pres, sufs), calc(t, pret, suft);
    for (int i = 1; i < n - 1 && s[i] == t[i]; i++) if (sufs[i + 1] == suft[i + 1])
        for (int j = 1; j < n - i; j++) if (Hash(ht, i + j + 1, n) == Hash(hs, i + 1, n - j) && Hash(ht, i + 1, i + j) == Hash(hs, n - j + 1, n))
            return void(cout << "YES\n1 " << i << '\n' << i + j + 1 << ' ' << n << '\n' << i + 1 << ' ' << i + j << '\n');
    for (int i = n - 1; i > 1 && s[i + 1] == t[i + 1]; i--) if (pres[i] == pret[i])
        for (int j = 1; j < i; j++) if (Hash(ht, j + 1, i) == Hash(hs, 1, i - j) && Hash(ht, 1, j) == Hash(hs, i - j + 1, i))
            return void(cout << "YES\n" << j + 1 << ' ' << i << "\n1 " << j << '\n' << i + 1 << ' ' << n << '\n');
    for (int i = 1; i < n - 1; i++) if (sufs[i + 1] == pret[n - i] && Hash(hs, 1, i) == Hash(ht, n - i + 1, n))
        for (int j = 1; j < n - i; j++) if (Hash(ht, j + 1, n - i) == Hash(hs, i + 1, n - j) && Hash(ht, 1, j) == Hash(hs, n - j + 1, n))
            return void(cout << "YES\n" << n - i + 1 << ' ' << n << '\n' << j + 1 << ' ' << n - i << "\n1 " << j << '\n');
    cout << "NO\n";
}
int main() {
    mt19937_64 rnd(760824); pw[0] = 1;
    for (int i = 1; i < N; i++) X[i] = rnd() % (P - 1) + 1, Y[i] = rnd() % (P - 1) + 1, pw[i] = _p(pw[i - 1], B);
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T; while (T--) solve();
}