51nod1089 最长回文子串 V2（Manacher算法/哈希）

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。
输入
输入Str（Str的长度 <= 100000)
输出
输出最长回文子串的长度L。
输入样例
daabaac
输出样例
5

知乎上 https://www.zhihu.com/question/37289584 ”c加加编程思想“ 答主的回答很棒。
思路：
简要阐述一下：
对照manacher的核心代码，其实就三部分，第一部分判断C与i的关系并进行状态转移，第二部分中心扩展（暴力！），第三部分维护C。
C是啥？转移啥？？请看下文

C = max{f[id] + id}，代表算出来的回文串的最大拓展范围。

n²到 n，中间需要利用已经算出来的信息，由此得出的马拉车算法，可以看做是动态规划。

将字符串翻倍后，定义f[j]为以j为中心的回文子串长度的一半。
按照dp思想，我们要计算的是f[i]，需要用到以前算过f[j]，并且计算f[j]的时候也要遵循同样的规则。

假设维护一个最大的值C，C = f[id] + id。再设j = 2 *id - i，代表j和i中心对称。f[i]和f[j]有一个转移关系，这就是我们需要找的子状态。

C > i时。
1 、假设i + f[j] ≤ C，那么意味着 j 对应的回文子串，i也一定对应着。
此时 f[i] = f[j]。
2、否则，我们最多只能算到C - i这么多,其他的部分只能暴力比较了。
那么取个min就好了。

C ≤ i，对称过去的 j 与 i 之前没有状态关系，那就只能暴力拓展啦。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 7;
char s1[maxn],s2[maxn];
int f[maxn];

int manacher(int len)
{
    int ans = 0,id = 1,mx = 0;
    for(int i = 1;i < len;i++)
    {
        if(id + mx > i)f[i] = min(f[id * 2 - i],id + mx - i);
        while(i - f[i] - 1 >= 1 && i + f[i] + 1 <= len && s2[i - f[i] - 1] == s2[i + f[i] + 1])
            f[i]++;
        if(id + mx < i + f[i])
        {
            id = i;mx = f[i];
        }
        ans = max(ans,f[i]);
    }
    return ans;
}

int main()
{
    scanf("%s",s1 + 1);
    int len = (int)strlen(s1 + 1);
    int len2 = 0;
    for(int i = 1;i <= len;i++)
    {
        s2[++len2] = '#';
        s2[++len2] = s1[i];
    }
    s2[++len2] = '#';
    printf("%d\n",manacher(len2));
    return 0;
}

再补上一个字符串哈希的算法

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;
const int maxn = 2e5 + 7;
const int mod = 29;

int p[maxn],hash_l[maxn],hash_r[maxn];
char tmp[maxn],s[maxn];

void get_hash(int len)
{
    p[0] = 1;
    for(int i = 1;i <= len;i++)p[i] = p[i - 1] * mod;
    for(int i = 1;i <= len;i++)hash_l[i] = hash_l[i - 1] * mod + s[i];
    for(int i = len;i >= 1;i--)hash_r[i] = hash_r[i + 1] * mod + s[i];
}

bool check(int i,int mid)
{
    int l = hash_l[i - 1] - hash_l[i - mid - 1] * p[mid];
    int r = hash_r[i + 1] - hash_r[i + mid + 1] * p[mid];
    if(l == r)return true;
    return false;
}

int main()
{
    scanf("%s",tmp + 1);
    int len = (int)strlen(tmp + 1);
    int len2 = 0;
    for(int i = 1;i <= len;i++)
    {
        s[++len2] = '#';
        s[++len2] = tmp[i];
    }
    s[++len2] = '#';
    
    get_hash(len2);
    
    int ans = 0;
    for(int i = 1;i <= len2;i++)
    {
        int l = 0,r = 0;
        if(i - 1 < len2 - i)r = i - 1;
        else r = len2 - i;
        int ans_t = 0;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(check(i,mid))
            {
                ans_t = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        ans = max(ans,ans_t);
    }
    printf("%d\n",ans);
    return 0;
}