| 歡迎關注__Xiong的部落格： http://blog.csdn.net/acmore_xiong?viewmode=list |
最長回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768
K (Java/Others)
Total Submission(s): 11760 Accepted Submission(s): 4308
連結：Click Me！
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
aaaa
abab Sample Output
4
3 分析：
求解最長回文串，曾經我是用DP來做的，在這個題目裡面，O(N^2)的複雜度肯定是會逾時的，于是我今天第一回敲了個Manacher的模闆，挺友善的，複雜度也降了一個數量級，複雜度僅僅有O（N）。Orz...
實作代碼：
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define CASE(T) int T;for(scanf("%d",&T);T--;)
const int maxn = 110000 + 5;
char Ma[maxn << 1];
int Mp[maxn << 1];
void Manacher(char s[], int len)
{
int l = 0;
Ma[l++] = '$';
Ma[l++] = '#';
for(int i = 0; i < len; i++)
{
Ma[l++] = s[i];
Ma[l++] = '#';
}
Ma[l] = 0;
int mx = 0, id = 0;
for(int i = 0; i < l; i++)
{
Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
if(i + Mp[i] > mx)
{
mx = i + Mp[i];
id = i;
}
}
}
char s[maxn];
int main()
{
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
while(~scanf("%s", s))
{
int len = strlen(s);
Manacher(s, len);
int ans = 0;
for(int i = 0; i < 2 * len + 2; i++)
{
ans = max(ans, Mp[i] - 1);
}
printf("%d
", ans);
}
return 0;
}