马拉车算法详解

Manachar算法：

因为上面这一片博客已经将Manachar讲的很清楚了，我就不再多做赘述，直接说下算法流程以及结论。

1.预处理：将字符串间隔插入一个不会在原串出现的字符，可以给开始字符记为$结尾字符记为^

1. 变量所携带的信息

2. p[i]表示以当前字符i开始，最长的回文子串的半径是多少。注意，P[i]所拥有的回文串都是奇数串。

3. mx表示回文串最远可以到达那里，
4. resLen，表示P[i]的最大值，也就是我们需要求的最长回文子串的长度，注意，p[i]所表示的值，总是会比我们真实的原串的回文子串的长度多1。

5. resCentre表示最长回文子串的中间位置，对应原串位置为整除2，不用考虑是否下取整，因为原串的每个字符在对应的扩展后的串中，都是在偶数下标下的。

6. p[i] = mx > i ? min(p[id * 2 - i], mx - i) : 1

p[i]没扩展的时候，只能在mx内取

while(b[i - p[i]] == b[i + p[i]]) p[i] ++;

扩展当前i的p数组

更新mx：只要当前p更新了，一定mx也更新了，毕竟mx是我们的边界

1. 然后返回所需信息

#include <bits/stdc++.h>
using namespace std;
const int N = 20000005;
char a[N], b[N];
int p[N];
int n;
void init()
{
  n = strlen(a);
  int k = 0;
  b[k ++ ] = '$', b[k ++ ] = '#';
  for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
  b[k ++ ] = '^';
  n = k;
  cout << b << endl;
}
int Manachar()
{
  int mx = 0, id = 0, resLen = 0, resCentre = 0;
  for (int i = 1; i < n; i ++ )
  {
    p[i] = mx > i ? min(p[id * 2 - i], mx - i) : 1;
    while (b[i - p[i]] == b[i + p[i]]) p[i] ++;
    if (mx < i + p[i])
    {
      mx = i + p[i];
      id = i;
    }
    if (resLen < p[i])
    {
      resLen = p[i];
      resCentre = i;
    }
  }
  return resLen - 1;
}
int main()
{
  cin >> a;
  init();
  cout << Manachar() << endl;
  return 0;
}