雙倍回文

金牌導(dǎo)航 manacher-2

luogu 4287

題目大意

設(shè)串為x，將其取反為x’，定義雙倍回文為形如xx’xx’的串
現(xiàn)在給你一個(gè)字符串，讓你求最大雙倍回文子串

輸入樣例

16 ggabaabaabaaball

輸出樣例

12

數(shù)據(jù)范圍

$N?10^5$

解題思路

對(duì)于該字符串，可以用manacher求回文子串，在求回文子串的同時(shí)判斷是否雙倍回文
對(duì)于通過(guò)對(duì)稱(chēng)得到最小回文長(zhǎng)度的，因?yàn)閷?duì)稱(chēng)，所以不用判斷
對(duì)于字符判斷使其回文長(zhǎng)度增加的，每增加一次就判斷一次
這樣就可以得到最大雙倍回文子串長(zhǎng)度了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 1000050 using namespace std; int n, p, mx, ans, v[N]; char s[N]; string str; int main() {scanf("%d", &n);cin>>str;s[0] = '/';s[1] = '#';for (int i = 1; i <= n; ++i)s[i * 2] = str[i - 1], s[i * 2 + 1] = '#';s[n * 2 + 2] = '|';n = n * 2 + 1;p = 1;mx = 1;for (int i = 1; i <= n; ++i){if (i < mx) v[i] = min(v[p * 2 - i], mx - i);//對(duì)稱(chēng)就不用判斷了else v[i] = 1;while(s[i - v[i]] == s[i + v[i]]){v[i]++;if (i&1 && v[i] % 4 == 0 && v[i - v[i] / 2] - 1 >= v[i] / 2)//判斷是否符合雙倍回文ans = max(ans, v[i]);//因?yàn)橛小?’乘除2就抵消了}if (i + v[i] > mx){mx = i + v[i];p = i;}}printf("%d", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【manacher】双倍回文（金牌导航 manacher-2/luogu 4287）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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