HDU 3608 最長回文

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

3

#include<cstdio>    
#include<cstring>    
#include<cmath>    
#include<algorithm>    
#include<queue>    
using namespace std;
typedef long long ll;
const int maxn = 110005;
char s[maxn], S[maxn * 2];
int f[maxn * 2];

int manacher(char *s)
{
  //字元串處理，增加分隔符
  int n = strlen(s);
  S[n + n + 2] = 0; S[0] = 2;
  for (int i = 0; s[i]; i++)
  {
    S[i + i + 3] = S[i + i + 1] = 1;
    S[i + i + 2] = s[i];
  }

  //manacher算法，計算出以每個字元為中心的最長回文串
  int mx = 0, id = 0, ans = 0;
  for (int i = 1; S[i]; i++)
  {
    if (mx > i) f[i] = min(f[id + id - i], mx - i);
    else f[i] = 1;
    while (S[i + f[i]] == S[i - f[i]]) f[i]++;
    if (f[i] + i > mx)
    {
      mx = f[i] + i;
      id = i;
    }
    ans = max(ans, f[i] - 1);
  }
  return ans;
}

int main()
{
  while (~scanf("%s", &s))
  {
    printf("%d\n", manacher(s));
  }
  return 0;
}