Manacher

马拉车算法

最大回文串

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

#define f(i, a, b) for (int i = a; i <= b; i++)
#define pn(x) printf("%d", x)
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define min(a, b) (a < b ? a : b)

int main()
{
    char s[] = "bdbuwahdkwjfkejsoboacaob";
    char *s_new = (char *)malloc(sizeof(char) * (2 * strlen(s) + 4));
    int j = 2;
    s_new[0] = '$';
    s_new[1] = '#';
    f(i, 0, strlen(s) - 1)
    {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
    s_new[j++] = '^';
    s_new[j] = '\0';
    /*形成新字符串*/
    int *p = (int *)malloc(sizeof(int) * (2 * strlen(s) + 4));
    p[1] = 0;
    int center=0, right = 0,maxlen=0,maxcenter;
    f(i, 2, strlen(s_new))
    {
        p[i] = i >= right ? 1 : min(right - i, p[2 * center - i]);
        while(s_new[i-p[i]]==s_new[i+p[i]]){
            p[i]++;
        }
        if(i+p[i]>right){
            right = i + p[i];
            center = i;
        }
        if(maxlen<p[i]){
            maxlen = p[i];
            maxcenter = i;
        }
    }
    /*输出结果*/
    pn(maxlen - 1);
    char *res = (char *)malloc(sizeof(char) * maxlen);
    j = 0;
    f(i, (maxcenter - maxlen) / 2, (maxcenter + maxlen) / 2 - 2)
        res[j++] = s[i];
    res[j] = '\0';
    printf("\n%s", res);
    return 0;
}