P3805 【模版】manacher算法

題目描述

給出一個(gè)只由小寫英文字符a,b,c...y,z組成的字符串S,求S中最長回文串的長度.

字符串長度為n

輸入輸出格式

輸入格式：

?

一行小寫英文字符a,b,c...y,z組成的字符串S

?

輸出格式：

?

一個(gè)整數(shù)表示答案

?

輸入輸出樣例

輸入樣例#1：
aaa 輸出樣例#1：
3

說明

字符串長度len <= 11000000

分析

str數(shù)組是原來的數(shù)組，s是后來的數(shù)組。

那樣例說，str：aaa，s：##a#a#a#，轉(zhuǎn)變的過程中的左移等位運(yùn)算模擬一下就會(huì)很清楚。

原先是一個(gè)一個(gè)賦值，s[k++] = '#',?str[k++] = s[i];結(jié)果tle最后一個(gè)點(diǎn)，改成位運(yùn)算好了。?

manacher模板

code

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define MAXN 31000000 5 using namespace std; 6 7 char s[MAXN],str[MAXN]; 8 int p[MAXN],len; 9 10 void init() 11 { 12 len = strlen(str); 13 s[0] = '#'; 14 for (int i=0; i<len; ++i) 15 { 16 s[i<<1|1] = '#'; 17 s[(i+1)<<1] = str[i]; 18 } 19 s[len<<1|1] = '#'; 20 len = (len<<1|1); 21 } 22 int manacher() 23 { 24 int mx = 0, id; 25 for (int i=1; i<=len; ++i) 26 { 27 if (mx>i) p[i] = min(p[id<<1-1],mx-i); 28 else p[i] = 1; 29 while (s[i+p[i]]==s[i-p[i]]) p[i]++; 30 if (p[i]+i>mx) 31 mx = p[i]+i, id = i; 32 } 33 int ans = 0; 34 for (int i=1; i<len; ++i) ans = max(ans,p[i]); 35 return ans-1; 36 } 37 int main() 38 { 39 scanf("%s",str); 40 init(); 41 printf("%d",manacher()); 42 return 0; 43 }

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

總結(jié)

以上是生活随笔為你收集整理的P3805 【模版】manacher算法（manacher）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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