View Code of Problem 197

#include <stdio.h>
#include <string.h>

#define maxn 2100

char s[maxn],s1[maxn];
int p[maxn];

int manacher(){
  int mx = 0, id = 0, mxx = -1;
  memset(p, 0, sizeof(p));
  for(int i = 1; s[i]; i++){
    int tmp = p[2*id-i] < (mx-i)?p[2*id-i] : (mx-i);
    p[i] = mx > i?tmp : 1;
    while(s[i + p[i]] == s[i - p[i]])
        p[i]++;
    if(i + p[i] > mx){
      mx = i + p[i];
      id = i;
    }
  }
  for(int i = 1; s[i]; i++)
    if(p[i] > mxx)
        mxx = p[i];
  return mxx - 1;
}

int main(){
  gets(s1);
  int tot = 1;
  s[0] = '$';
  for(int i = 0; s1[i]; i++){
    s[tot++] = '#';
    s[tot++] = s1[i];
  }
  s[tot] = '#';
  int ans = manacher();
  printf("%d\n", ans);
  return 0;
}