二分+字符串哈希

字符串哈希

先说一维字符串哈希。基本思想是对每个 \(i\)，先求出 \([1,i]\) 上字符串哈希的值（前缀和思想），然后使用类似差分的方法求出 \([x,y]\) 上字符串哈希的值。
具体算法：\(h[i]=(\sum \limits_{j=1}^i s_j \times P^{i-j}) \% Q\)。
例如 \(h[ABCD]=(A \times P^3 + B \times P^2 + C \times P^1 + D \times P^0) \% Q\)。
注意为什么不是顺着乘 \(12345\)，而是倒着乘 \(54321\)，因为差分的时候要做除法，预处理对于 \(2^{64}\) 的逆元很难办，所以倒着乘！
一般选择的 \(P\) 为 \(13331\)，\(Q\) 为 \(2^{64}\)（用 unsigned long long 存可以自动取模）哈希冲突的几率比较小。（我们此算法不会考虑哈希表处理哈希冲突，但是要考虑也是可以的）

递推式：
\(h[i] = h[i - 1] \times P + s_i\)
差分方法：
\(h[(i,j)] = h[j] - h[i] \times P^{j-i+1}\)
预处理 \(P^i\)。
时间复杂度：预处理 \(O(n)\)，查询 \(O(1)\)。
空间复杂度：\(O(n)\)。

再扩展到二维哈希。
依然使用二维前缀和的思想，横纵的 \(P\) 值不要相同即可。
\(h[i][j]=(\sum \limits_{x=1}^i \sum\limits_{y=1}^j s_{ij} \times P_1^{i-x} \times P_2^{j-y}) \% Q\)
\(h[i][j]=h[i-1][j] \times P_1+h[i][j - 1] \times P_2 - h[i - 1] [j- 1] \times P_1 \times P_2 + s_{ij}\)
\(h[(i,k)][(j,l)] = h[k][l] - h[i - 1][l] \times P_1^{k - i + 1} - h[k][j - 1] \times P_2^{l - j + 1} + h[i - 1][j - 1] \times P_1^{k - i + 1}\times P_2^{l - j + 1}\)

URAL 1486

题意：给定 \(n \times m\) 的字符矩阵，求最大的 \(l\)，使得两个边长为 \(l\) 的字符正方形完全相同。这两个正方形可以重叠，但不能重合。
\(1 \le n, m \le 500\)。

注意到一个性质：如果存在以 \((x,y)\) 为左上角，\(l\) 为边长的这样的三角形，那么一定存在以 \((x,y)\) 为左上角，\(0 \sim l-1\) 为边长的这样的三角形。也就是有可二分性。

对于本题，二分+哈希（二哈）。二分正方形的长度，枚举左上角，哈希值放到 map 里面，判断是否存在重复的即可。对于哈希值由于预处理了 power(p)，所以可以 \(O(1)\) 获得。
时间复杂度 \(O(n^2 \log n)\)。

以下实现采用快速幂多了一个 log，也能过。

#include<bits/stdc++.h>
using namespace std;
#define f(i, a, b) for(unsigned long long i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int inf = 1e9;
ull p1 = 1777, p2 = 17737;
ull pow1[510], pow2[510], inv1[510], inv2[510];
char c[510][510];
ull h[510][510];
int ansx1[510], ansy1[510], ansx2[510], ansy2[510];
map<ull, pair<int, int>> mp; 
ull n, m;
ull qpow(ull x, ull k) {
    ull ans = 1;
    while(k) {
        if(k & 1) ans = ans * x;
        x = x * x;
        k >>= 1;
    }
    return ans;
}
bool ok(int len) {
    if(len == 0) return 1;
    f(i, 1, n) f(j, 1, m) {
        int k = i + len - 1, l = j + len - 1;
        if(k > n || l > m) continue;
        ll ha = h[k][l]-h[i-1][l]*pow1[k-i+1]-h[k][j-1]*pow2[l-j+1]+h[i-1][j-1]*pow1[k-i+1]*pow2[l-j+1];
        if(mp.count(ha)) {
            ansx1[len] = mp[ha].first, ansy1[len] = mp[ha].second; 
            ansx2[len] = i, ansy2[len] = j; return 1;
        }
        mp[ha] = make_pair(i, j);
    }

    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
     cin >> n >> m;
    pow1[0] = pow2[0] = 1;
    f(i, 1, 500) {
        pow1[i] = pow1[i - 1] * p1;
        inv1[i] = qpow(pow1[i], p1 - 2);
        pow2[i] = pow2[i - 1] * p2;
        inv2[1] = qpow(pow2[i], p2 - 2);
    }
    f(i, 1, n) f(j, 1, m) cin >> c[i][j];
    f(i,1 ,n) f(j, 1, m) {
        h[i][j] = h[i-1][j]*p1+h[i][j-1]*p2-h[i-1][j-1]*p1*p2+c[i][j];
    }
    int l = 0, r = min(n, m);
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(ok(mid)) l = mid;
        else r = mid -1;
    }
    cout << l << endl;
    if(l != 0) {
        cout << ansx1[l] << " " << ansy1[l] << endl << ansx2[l] << " " << ansy2[l] << endl;
    }
    return 0;
}

acwing139

求一个字符串回文子串的最大长度。

\(n \le 10^6\)

枚举中间位置，对于奇数和偶数个字符的回文串分别考虑。

时间复杂度 \(O(n \log n)\)。
更优秀的做法：manacher，\(O(n)\)。

acwing140

后缀排序。

\(n \le 3 \times 10^5\)

直接排序，对于每次比较二分相等字符的个数并 \(O(1)\) 判断。因此每次比较的时间复杂度为 \(O(\log n)\)，总时间复杂度 \(O(n \log^2 n)\)。

更优秀的做法：倍增法比较，\(O(n \log^2 n)\)，基数排序优化 \(O(n \log n)\)，SA-IS \(O(n)\)。