最長回文

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)

Problem Description 給出一個只由小寫英文字符a,b,c...y,z組成的字符串S,求S中最長回文串的長度.
回文就是正反讀都是一樣的字符串,如aba, abba等
Input 輸入有多組case,不超過120組,每組輸入為一行小寫英文字符a,b,c...y,z組成的字符串S
兩組case之間由空行隔開(該空行不用處理)
字符串長度len <= 110000
Output 每一行一個整數x,對應一組case,表示該組case的字符串中所包含的最長回文長度.

Sample Input aaaaabab
Sample Output 4 3 這個題我先用后綴數組+最長公共前綴做的，但是超時了（可能是我的代碼寫的太爛了）。后來搜題解，才發現大家都是用manacher算法做的，時間復雜度為O(n)。第一次聽說這個算法，于是就學了一下。

定義數組p[i]表示以i為中心的(包含i這個字符)回文串半徑長

將字符串s從前掃到后for(int?i=0;i<strlen(s);++i)來計算p[i],則最大的p[i]就是最長回文串長度,則問題是如何去求p[i]?

由于s是從前掃到后的,所以需要計算p[i]時一定已經計算好了p[1]....p[i-1]

假設現在掃描到了i+k這個位置,現在需要計算p[i+k]

定義maxlen是i+k位置前所有回文串中能延伸到的最右端的位置,即maxlen=p[i]+i;//p[i]+i表示最大的

分兩種情況:

1.i+k這個位置不在前面的任何回文串中,即i+k>maxlen,則初始化p[i+k]=1;//本身是回文串

然后p[i+k]左右延伸,即while(s[i+k+p[i+k]]?==?s[i+k-p[i+k]])++p[i+k]

2.i+k這個位置被前面以位置i為中心的回文串包含,即maxlen>i+k

這樣的話p[i+k]就不是從1開始

由于回文串的性質,可知i+k這個位置關于i與i-k對稱,

所以p[i+k]分為以下3種情況得出

//黑色是i的回文串范圍,藍色是i-k的回文串范圍,

根據上面的算法可以得出：p[i]是以i為中心的回文串長度，那么對于aaaa這樣的字符串求回文字符串時發現對稱中心不是一個字符，而是空的，所以要把偶數字符串變成奇數字符串，方法就是在字符串中插入字符串中沒有出現過的字符，例如‘#‘。

核心代碼：

for(int i = 1; i < len; i++) {p[i] = mmax > i ? min(p[id*2-i], mmax - i) : 1;while(s[i+p[i]] == s[i-p[i]]) p[i]++;if(i + p[i] > id + p[id]) {id = i;mmax = i + p[i];} }最長回文長度就是mmax-1。

p[i]為回文半徑，如果該半徑以’#‘開始，即回文串為'#''s[i]'#'……'#'，則一定以'#'結束，所以mmax-1以后'#'和's[]'一樣多，即mmax-1是原串以i為中心的回文字符串長度。如果該半徑是以s[]開始的，即's[]''#'……'#''s[]'，則回文串長度是p[i]-1。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 220005; char str[N]; int p[N];void manacher(char *s, int len) {p[0] = 1;int mmax = 0, id = 0;for(int i = 1; i < len; i++) {p[i] = mmax > i ? min(p[id*2-i], mmax - i) : 1;while(s[i+p[i]] == s[i-p[i]]) p[i]++;if(i + p[i] > id + p[id]) {id = i;mmax = i + p[i];}} }int main() {while(~scanf("%s",str)) {int len = strlen(str);for(int i = len; i >= 0; i--) {str[(i<<1) + 1] = '#';str[(i<<1) + 2] = str[i];}str[0] = '*'; //防止數組越界len = len * 2 + 2;manacher(str, len);int ans = 0;for(int i = 0; i < len; i++)ans = max(ans, p[i]-1);printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3068 最长回文（manacher算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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