Problem Description

最后來(lái)個(gè)字符串簽個(gè)到吧，這題其實(shí)并不難，所需的算法比較基礎(chǔ)，甚至你們最近還上過(guò)課。

為了降低難度，免得所有人爆零。這里給幾個(gè)提示的關(guān)鍵字 ：字符串，回文，二分，哈希. 注意要對(duì)奇偶回文分開(kāi)二分

這樣還不會(huì)做，說(shuō)明基礎(chǔ)有所欠缺。

給你一個(gè)字符串A和一個(gè)字符串B,請(qǐng)你求一個(gè)滿足以下要求的所有字符串中，最長(zhǎng)的字符串C的長(zhǎng)度：

C必須同時(shí)是A和B的子串，即A和B中都必須存在一個(gè)子區(qū)間和C長(zhǎng)得一樣

C必須是一個(gè)回文，即正過(guò)來(lái)讀和反過(guò)來(lái)讀都一樣

?

Input

多組數(shù)據(jù)，請(qǐng)?zhí)幚淼紼OF

每組數(shù)據(jù)包含，兩行，每行都是僅由小寫(xiě)字符構(gòu)成的字符串，代表A和B。

對(duì)于30%的數(shù)據(jù)。

保證|A|,|B|<=1000，且單個(gè)文件的字符總數(shù)小于10000

對(duì)于100%的數(shù)據(jù)

保證|A|,|B|<=100000，且單個(gè)文件的字符總數(shù)小于2e6

其中70%的數(shù)據(jù)答案為奇數(shù)哦

因?yàn)闆](méi)有處理掉字符串尾巴上多余的'\r',所以為了防止讀到'\r' 推薦使用scanf("%s");

鏈接

?

思路：

?更新2.0：

旺神nb。發(fā)現(xiàn)A了之后就能看所有人代碼了

終于找到Hash的O(n)找公共子串的方法了，直接用unordered_map儲(chǔ)存所有滿足長(zhǎng)度的回文子串。unordered_map查詢接近常數(shù)級(jí)，就是O（1），插入反正比map快，所以總體就是O（n）級(jí)。

然后就從7000ms瞬間降到1400ms

代碼2.0我沒(méi)有預(yù)處理成全奇回文，而是直接分類奇偶二分。顯然我們可以優(yōu)化一下，奇偶遍歷存在與否時(shí)可以直接兩步兩步走，因?yàn)槠媾嫉幕匚闹行膭偤媒诲e(cuò)。然后我們假如先二分奇數(shù)，得到一個(gè)長(zhǎng)度R，那么我二分偶數(shù)回文半徑至少R / 2 + 1，否則沒(méi)有意義。我們直接用unordered_map儲(chǔ)存s串的回文答案，然后O（n）判斷p中有沒(méi)有，如果怕Hash沖突，可以再驗(yàn)算一邊是否一樣。

然后我發(fā)現(xiàn)時(shí)限變成4000ms了...7s的代碼卡掉了...只能用2.0的代碼過(guò)...

這道題后綴數(shù)組也能做，JQtxdy +?

----------------代碼1.0分割線（已T）----------------------------

按照旺神的思路來(lái)。

我是把串先按照Manacher處理成只有奇數(shù)回文，然后找到最大回文串R，顯然最終答案只可能是R，R-2，R-4....那么我直接二分這個(gè)最終長(zhǎng)度。然后用hash找是否存在這個(gè)長(zhǎng)度的公共子串，但是我只會(huì)Hash的O（nlogn + m）寫(xiě)法啊。在T了幾發(fā)之后發(fā)現(xiàn)題目時(shí)限又開(kāi)大了，8000ms用7400ms擦過(guò)，旺神nb。

代碼2.0：

#include<cmath> #include<set> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include <iostream> #include<algorithm> #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 200000 + 10; const ull seed = 131; const int INF = 0x3f3f3f3f; const int MOD = 1000000007; char s[maxn], p[maxn], snew1[maxn]; int pos[maxn], num[maxn]; ull hs[maxn], hp[maxn], fac[maxn], q[maxn]; inline ull getHashP(int l, int r){return hp[r] - (l == 0? 0 : hp[l - 1]) * fac[r - l + 1]; } inline ull getHashS(int l, int r){return hs[r] - (l == 0? 0 : hs[l - 1]) * fac[r - l + 1]; } int lens, lenp, lenSnew; int init(int len){int cnt = 0;snew1[cnt] = '$';for(int i = 0; i < len; i++){snew1[++cnt] = '#';snew1[++cnt] = s[i];}snew1[++cnt] = '#';snew1[++cnt] = '\0';return cnt; } int Manacher(){int cnt = init(lens);lenSnew = cnt;int id = 0, ans = -1;for(int i = 2; i < cnt; i++){if(pos[id] + id > i){pos[i] = min(pos[2 * id - i], pos[id] + id - i);}else pos[i] = 1;while(snew1[i - pos[i]] == snew1[i + pos[i]])pos[i]++;if(id + pos[id] < i + pos[i])id = i;ans = max(ans,pos[i] - 1);}return ans; //長(zhǎng)度 } bool mid(int l, int r, ull aim){while(l <= r){int m = (l + r) >> 1;if(q[m] >= aim){if(q[m] == aim) return true;r = m - 1;}else l = m + 1;}return false; } unordered_map<ull, int> mp; //$#a#a#a#0 bool checkJi(int len){mp.clear();for(int i = 2; i + len - 1 < lenSnew; i += 2){ //sif(pos[i] - 1 >= len){int R = len / 2;int position = i / 2 - 1; //實(shí)際位置mp[getHashS(position - R, position + R)] = 1;}}for(int i = 0; i + len - 1 < lenp; i++){ull aim = getHashP(i, i + len - 1);if(mp.count(aim)) return true;}return false; } //$#c#a#a#a#a#0 bool checkOu(int len){mp.clear();for(int i = 1; i + len - 1 < lenSnew; i += 2){ //sif(pos[i] - 1 >= len){int R = len / 2;int position = i / 2 - 1; //實(shí)際位置mp[getHashS(position - R + 1, position + R)] = 1;}}for(int i = 0; i + len - 1 < lenp; i++){ull aim = getHashP(i, i + len - 1);if(mp.count(aim)) return true;}return false; } int main(){fac[0] = 1;for(int i = 1; i < 100010; i++)fac[i] = fac[i - 1] * seed;while(scanf("%s%s", s, p) != EOF){lens = lenp = 0;hs[0] = hp[0] = 0;for(int i = 0; s[i] != '\0'; i++){ //hashif(i == 0) hs[i] = s[i];else hs[i] = hs[i - 1] * seed + s[i];lens++;}for(int i = 0; p[i] != '\0'; i++){if(i == 0) hp[i] = p[i];else hp[i] = hp[i - 1] * seed + p[i];lenp++;}int R = Manacher(); //馬拉車返回s最大長(zhǎng)度int l, r, ans = 0;l = 1, r = R / 2;while(l <= r){ //偶int m = (l + r) >> 1;if(checkOu(m * 2)){l = m + 1;ans = m * 2;}else r = m - 1;}l = ans / 2, r = R / 2;while(l <= r){ //奇int m = (l + r) >> 1;if(checkJi(m * 2 + 1)){l = m + 1;ans = max(m * 2 + 1, ans);}else r = m - 1;}printf("%d\n", ans);}return 0; }

?

代碼：

#include<cmath> #include<set> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include <iostream> #include<algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 200000 + 10; const ull seed = 131; const int INF = 0x3f3f3f3f; const int MOD = 1000000007; char s[maxn], p[maxn], snew1[maxn], snew2[maxn]; int pos[maxn], num[maxn]; ull hs[maxn], hp[maxn], fac[maxn], q[maxn]; inline ull getHashP(int l, int r){return hp[r] - (l == 0? 0 : hp[l - 1]) * fac[r - l + 1]; } inline ull getHashS(int l, int r){return hs[r] - (l == 0? 0 : hs[l - 1]) * fac[r - l + 1]; } int lens, lenp, lenSnew; int init(int len){int cnt = 0;snew1[cnt] = '$';for(int i = 0; i < len; i++){snew1[++cnt] = '#';snew1[++cnt] = s[i];}snew1[++cnt] = '#';snew1[++cnt] = '\0';return cnt; } int Manacher(){int cnt = init(lens);lenSnew = cnt;int id = 0, ans = -1;for(int i = 2; i < cnt; i++){if(pos[id] + id > i){pos[i] = min(pos[2 * id - i], pos[id] + id - i);}else pos[i] = 1;while(snew1[i - pos[i]] == snew1[i + pos[i]])pos[i]++;if(id + pos[id] < i + pos[i])id = i;ans = max(ans,pos[i] - 1);}return ans; //長(zhǎng)度 } bool mid(int l, int r, ull aim){while(l <= r){int m = (l + r) >> 1;if(q[m] >= aim){if(q[m] == aim) return true;r = m - 1;}else l = m + 1;}return false; } bool check(int len){int tol = 0;for(int i = 0; i + len - 1 < lenp; i++){ //p子串q[tol++] = getHashP(i, i + len - 1);}sort(q, q + tol);for(int i = 2; i < lenSnew; i += 2){ //找sif(pos[i] - 1 >= len){int R = len / 2;int position = i / 2 - 1; //實(shí)際位置ull aim = getHashS(position - R, position + R);if(mid(0, tol - 1, aim)){return true;}}}return false; } int main(){fac[0] = 1;for(int i = 1; i < maxn; i++)fac[i] = fac[i - 1] * seed;while(scanf("%s%s", snew1, snew2) != EOF){lens = 0, lenp = 0;//改成全奇回文s[lens++] = '0';for(int i = 0; snew1[i] != '\0'; i++){s[lens++] = snew1[i];s[lens++] = '0';}p[lenp++] = '0';for(int i = 0; snew2[i] != '\0'; i++){p[lenp++] = snew2[i];p[lenp++] = '0';}hs[0] = hp[0] = 0;for(int i = 0; i < lens; i++){ //hashif(i == 0) hs[i] = s[i];else hs[i] = hs[i - 1] * seed + s[i];}for(int i = 0; i < lenp; i++){if(i == 0) hp[i] = p[i];else hp[i] = hp[i - 1] * seed + p[i];}int cnt = lenSnew;int L = 1, R = Manacher(); //馬拉車返回最大長(zhǎng)度int l = 1, r = R / 2; //R = 2 * r + 1int ans = 0;while(l <= r){int m = (l + r) >> 1;if(check(2 * m + 1)){ans = 2 * m + 1;l = m + 1;}else{r = m - 1;}}printf("%d\n", ans / 2);}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/10663751.html

總結(jié)

以上是生活随笔為你收集整理的FJUT3703 这还是一道数论题（二分 + hash + manacher 或者 STL + hash 或者 后缀数组 + hash）题解...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。