～～～題面～～～

題解：

首先有一個直觀的想法，如果我們可以求出對于位置i的最長后綴回文串和最長前綴回文串，那么我們枚舉分界點然后合并前綴和后綴不就可以得到答案了么？

所以我們的目標就是求出這兩個數列，

我們令f[i] 表示以i為結尾的最長回文后綴的長度，g[i]表示以i為開頭的最長回文后綴的長度。

由于要找回文串，因此我們先想到manacher。

然后我們可以發現對于這樣一個串：

原串：xxxxxxxxxx

新串：#x#x#x#x#x#x#x#x#x#x#

我們可以觀察到，假設這時我們已經求出了f和g，那么對于任意位置而言，合并出的最長雙回文串中，都是“偶串”，且有一半是'#',一半是原串。

因此我們可以直接合并f[i-1] 和 g[i],并用ans記錄最大值，那么這時真正的答案就是ans / 2.

假設我們manacher已經求到了第i位，此時i的最長回文半徑是R，且j已經被包括在R里面了，那么顯然i對j的貢獻是(j - i) * 2 + 1。

而因為貢獻只和i與j的位置有關，并且我們的i是從1開始，逐漸遞增的，因此對于任意一個j，第一次將它更新的i必然可以產生最優解，因此每個j會且僅會被更新一次。

而被更新的j顯然也是遞增的，因為如果j后面的k已經被更新的話，說明之前已經有一個i可以使得k被覆蓋在內了。那么j既然在k前面，肯定也被覆蓋過了，

因此求出f[j]時，j肯定是遞增的（也就是說肯定是先求出前面的在求出后面的），因此我們可以直接維護一個指針t（這個指針只是字面上的指針），表示當前已經更新到了t，

一旦被覆蓋的MaxRight > t,我們就直接用當前的i來更新t。

對于前綴回文串，我們直接把字符串翻轉過來，然后再做一遍相同的操作，再把得到的數組反轉回來就可以了

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 202000 5 /*處理出前綴半徑和后綴半徑，然后合并。可以發現，在擴充了數列之后（#）， 6 獲取的最長雙回文串一定是偶串，且# 和 真實字符數量相同。 7 因此ans就是合并后的最長長度/2*/ 8 int n, pos, maxn, ans; 9 int f[AC], g[AC], tmp[AC], r[AC]; 10 char s[AC], p[AC]; 11 12 void pre()//讀入 13 { 14 scanf("%s", s + 1); 15 n = strlen(s + 1); 16 for(R i = n; i; --i) s[i * 2] = s[i]; 17 n = 2 * n + 1; 18 for(R i = 1; i <= n; i += 2) s[i] = '#'; 19 for(R i = 1; i <= n; i++) p[i] = s[n - i + 1];//把原串倒過來做一遍就是后綴了 20 s[0] = p[0] = '$', s[n + 1] = p[n + 1] = '$'; 21 } 22 23 void build()//處理出前綴半徑和后綴半徑 24 { 25 int t = 0; 26 pos = maxn = 0; 27 for(R i = 1; i <= n; i++) 28 { 29 r[i] = maxn > i ? min(r[2 * pos - i], maxn - i + 1) : 1; 30 while(s[i - r[i]] == s[i + r[i]]) ++r[i]; 31 if(i + r[i] - 1 > maxn) 32 { 33 maxn = i + r[i] - 1, pos = i; 34 if(maxn > t)//更新后綴 35 { 36 for(R j = t + 1; j <= maxn; j++) f[j] = (j - i) * 2 + 1; 37 t = maxn; 38 } 39 } 40 } 41 pos = maxn = t = 0; 42 for(R i = 1; i <= n; i++) 43 { 44 r[i] = maxn > i ? min(r[2 * pos - i], maxn - i + 1) : 1; 45 while(p[i - r[i]] == p[i + r[i]]) ++r[i]; 46 if(i + r[i] - 1 > maxn) 47 { 48 maxn = i + r[i] - 1, pos = i; 49 if(maxn > t)//更新后綴 50 { 51 for(R j = t + 1; j <= maxn; j++) tmp[j] = (j - i) * 2 + 1; 52 t = maxn; 53 } 54 } 55 } 56 for(R i = 1; i <= n; i++) g[i] = tmp[n - i + 1]; 57 // for(R i = 1; i <= n; i++) printf("%d ", f[i]); 58 // printf("\n"); 59 } 60 61 inline void upmax(int &a, int b) 62 { 63 if(b > a) a = b; 64 } 65 66 void work()//合并 67 { 68 for(R i = 1; i <= n; i++) 69 upmax(ans, f[i - 1] + g[i]); 70 printf("%d\n", ans/2); 71 } 72 73 int main() 74 { 75 freopen("in.in", "r", stdin); 76 pre(); 77 build(); 78 work(); 79 fclose(stdin); 80 return 0; 81 }

?

轉載于:https://www.cnblogs.com/ww3113306/p/9382938.html

總結

以上是生活随笔為你收集整理的[国家集训队]最长双回文串 manacher的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。