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

manacher练手题

#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;
}