題面：

　　洛谷：[SHOI2011]雙倍回文‘

題解：

　　首先有一個(gè)性質(zhì)，本質(zhì)不同的回文串最多O(n)個(gè)。

　　所以我們可以對(duì)于每個(gè)i，求出以這個(gè)i為結(jié)尾的最長(zhǎng)回文串，然后以此作為長(zhǎng)串，并判斷把這個(gè)長(zhǎng)串從中間劈開(kāi)后左邊的一半是否也是一個(gè)回文串（判斷左邊那半的中點(diǎn)的回文半徑是否可以跨過(guò)當(dāng)前長(zhǎng)串的中點(diǎn)）。

　　復(fù)雜度O(n)

1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define R register int 5 #define AC 1001000 6 7 int n, pos, maxn, ans; 8 int r[AC]; 9 char a[AC], s[AC]; 10 11 void pre(){ 12 scanf("%d%s", &n, a + 1); 13 s[0] = '$', s[1] = '#'; 14 for(R i = 1; i <= n; i ++) s[2 * i] = a[i], s[2 * i + 1] = '#'; 15 } 16 17 inline void upmax(int &a, int b){ 18 if(b > a) a = b; 19 } 20 21 void manacher() 22 { 23 int b = 2 * n; 24 for(R i = 1; i <= b; i ++) 25 { 26 r[i] = (maxn > i) ? min(r[2 * pos - i], maxn - i + 1) : 1;//這里要取min 27 while(s[i - r[i]] == s[i + r[i]]) ++ r[i]; 28 29 int last = i - r[i] + 1, Next = i + r[i] - 1; 30 if(s[last] == '#') ++ last, -- Next; 31 if(i + r[i] - 1 > maxn && last <= i)//last才是整個(gè)串的開(kāi)頭 32 { 33 for(R j = maxn + 1; j <= Next; j ++) 34 { 35 int l = 2 * i - j;//獲取串頭 36 int sum = (j - l + 1 + 1) >> 1; 37 if(s[j] == '#' || sum % 4) continue;//中間是獲取實(shí)際字符數(shù) 38 int tmp = (l + j) >> 1, k = (tmp + l) >> 1; 39 if(k + r[k] - 1 >= tmp) upmax(ans, sum); 40 } 41 } 42 43 if(i + r[i] - 1 > maxn) pos = i, maxn = i + r[i] - 1; 44 } 45 printf("%d\n", ans); 46 } 47 48 int main() 49 { 50 //freopen("in.in", "r", stdin); 51 pre(); 52 manacher(); 53 //fclose(stdin); 54 return 0; 55 } View Code

?

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

總結(jié)

以上是生活随笔為你收集整理的[SHOI2011]双倍回文 manacher的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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