【OI】hash在字元匹配的妙用[Jsoi2016]扭動的迴文串

傳送門：[Jsoi2016]扭動的迴文串

題意：給出兩個字元串A串和B串，可以將A串的[i,k]切出來，和B串的[k,j]拼在一起，組成新的字元串，求最長的A串內或B串內或經過以上操作的字元串內的最長迴文串

數學語言：對於切割的字元串，求 （check是判斷是否為迴文串的bool函數）

數據範圍：

這道題時間複雜度 的演算法應該是很顯然的，用manachar先掃一遍A串和B串記錄ans然後枚舉切割點每一次做一遍manachar即可。聽說有很可觀的暴力分（貌似能A（霧））

然而蒟蒻題主只會這種暴力哎

然後就看了看WerKeyTom_FTD的blog，不愧是棟爺我剛開始真的是看不懂qwq，不過後來偶然翻到了劉汝佳的藍書3.4.3（如果你和我版本一樣應該是P224頁）基於hash的LCP演算法，我才發現原來棟爺用的就是hash加二分答案（不過他好像寫了只是我hash太菜沒看懂）。

所以我就來講一下這種判法，看看有沒有hash跟我一樣菜的不知道這種辦法。（大概沒有qwq）

對於一個字元串的hash，我想你們應該也是知道的，就比如說找一段文章中有哪個單詞出現了最多次，你就可以把字元串每一位hash掉，具體hash值的演算法應該就是 ，這裡的p一般取的是字母的種類數，就像十進位存數一樣，如果是嚴格的26個字母，你可以讓 ，這樣就能避免不同的位數互相影響。

寫成代碼大概就是醬紫的：

for (int i = 1; i <= len; i++) c[i] = c[i] - A;//將字母壓成0~25的數字int sum = 0;for (int i = 1; i <= len; i++) sum = (sum + c[i] * p) % mod;

可是我們要求的是一段區間的字母的hash值呀，難道你能將hash值按前綴和操作？

其實還真的可以。不過後綴和會更好操作哎。

對於一個到 的字元串，記hash值為 ，則容易寫出 的表達式：

那麼也容易得到 的值

兩式相減：

右邊即是c[i]的hash值

類似的手法，我們很容易得到 的的值，為了消掉無關項，我們要先將 乘個 ，使得 內的 與 的齊次：

接著兩式相減：

這便是一個獨屬於區間 的hash值啦！

我們可以通過預處理字元串的後綴和和預處理 ，在每次判斷的時候寫一個check函數可以做到 的效率，枚舉A串和B串的起始點，先在本串擴展，然後連接另一個串。具體的話。。。我來舉一個例子：

A串：

B串：

例如你在枚舉到A串的第四個字母C的時候，你會先訪問A的manachar結果，發現這個C本身是迴文子串ACA的中心，那麼更改現在子串為ACA（可以證明這是最優的，如果B串本身也能做到與A串匹配，但即便這樣也是與A串直接擴展等價的（想一想為什麼）），接著你就鎖定了A串第二個字元D和B串的第五個字元D，這裡因為我們hash判斷是 的效率，我們不妨二分可以進行擴展的子串長度，對於每次擴展hash判斷，便使擴展的複雜度變成了 級別的，所以總複雜度為 。

#include<bits/stdc++.h>#define fo(i, a, b) for (R int i = (a); i <= (b); i++)#define fd(i, a, b) for (R int i = (a); i >= (b); i--)#define R register#define N 200105#define in inline//#define debug#define mod1 122777#define mod2 388211#define ll long longll nn, n, a[N], b[N], fa[N], fb[N], ans, ha[N][2] ,hb[N][2], mi[N][2];in char gchar (){ char ch = std::getchar(); while (ch >Z || ch < A) ch = std::getchar(); return ch; }in bool check (ll l1, ll r1, ll l2, ll r2){ ll x = (ha[r1][0] - ha[l1 - 1][0] * mi [r1 - l1 + 1][0] % mod1) % mod1; ll y = (hb[l2][0] - hb[r2 + 1][0] * mi [r2 - l2 + 1][0] % mod1) % mod1; x = (x + mod1) % mod1; y = (y + mod1) % mod1; if (x != y) return 0; x = (ha[r1][1] - ha[l1 - 1][1] * mi [r1 - l1 + 1][1] % mod2) % mod2; y = (hb[l2][1] - hb[r2 + 1][1] * mi [r2 - l2 + 1][1] % mod2) % mod2; x = (x + mod2) % mod2; y = (y + mod2) % mod2; return (x == y);}in ll solve (ll x, ll y){ ll l = 0, r = std::min(x, n - y + 1); while (l < r) { ll mid = (l + r + 1) >> 1; if (check(x - mid + 1, x, y, y + mid - 1)) l = mid; else r = mid - 1; } return l;}int main(){#ifdef debug freopen("miao.txt", "r", stdin);#endif scanf("%lld", &n); fo (i, 1, n) a[i << 1] = gchar() - A; fo (i, 1, n) b[i << 1] = gchar() - A; fo (i, 0, n) b[(i << 1) + 1] = a[(i << 1) + 1] = 27; a[0] = b[0] = 233; n = n << 1; a[n + 1] = b[n + 1] = 27; a[n + 2] = b[n + 2] = 2333; int j = 0; fo (i, 1, n) { if (fa[j] + j > i) fa[i] = std::min(fa[(j << 1) - i], j + fa[j] - i); while (a[i + fa[i]] == a[i - fa[i]]) fa[i]++; fa[i]--; if (fa[i] + i > fa[j] + j) j = i; } j = 0; fo (i, 1, n) { if (fb[j] + j > i) fb[i] = std::min(fb[(j << 1) - i], j + fb[j] - i); while (b[i + fb[i]] == b[i - fb[i]]) fb[i]++; fb[i]--; if (fb[i] + i > fb[j] + j) j = i; } fo (i, 1, n) ans = std::max(ans, std::max(fa[i], fb[i])); n = n >> 1; mi[0][0] = mi[0][1] = 1; fo (i, 1, n) { mi[i][0] = mi[i - 1][0] * 27 % mod1; mi[i][1] = mi[i - 1][1] * 27 % mod2; } ha[0][0] = ha[0][1] = 1; fo (i, 1, n) { ha[i][0] = (ha[i - 1][0] * 27 + a[i << 1]) % mod1; ha[i][1] = (ha[i - 1][1] * 27 + a[i << 1]) % mod2; } hb[n + 1][0] = hb[n + 1][1] = 1; fd (i, n, 1) { hb[i][0] = (hb[i + 1][0] * 27 + b[i << 1]) % mod1; hb[i][1] = (hb[i + 1][1] * 27 + b[i << 1]) % mod2; } ll l, r; nn = n << 1; fo (i, 2, nn) { l = i - fa[i]; r = i + fa[i]; l = l + 1 >> 1; r = r >> 1;#ifdef debug printf("l = %lld, r = %lld
", l, r);#endif ans = std::max(ans, fa[i] + (solve(l - 1, r) << 1)); } fo (i, 2, nn) { l = i - fb[i]; r = i + fb[i]; l = l + 1 >> 1; r = r >> 1; ans = std::max(ans, fb[i] + (solve(l, r + 1) << 1)); } printf("%lld", ans); return 0;}

然而題主太懶了懶得打注釋。。。其實難點主要我覺得是二分答案的細節太多了，注意一下各種邊界的處理多調幾次就行。

本文為蒟蒻所作，若有語言欠妥之處，請在評論區指出，謝謝。

若要轉載請註明出處。