马拉车算法（线性求回文串）

参考博客

AC代码（模板）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 4e5 + 10;
char s[maxn], tmp[maxn];
int dp[maxn];
char change(char x, char a){
    return (x - a + 26) % 26 + 'a';
}
///转化方式思想来自对一个圈的点标号（知道取模之后就可以自己推一下）
int main(){
    char a[5];
    while(scanf("%s%s", a, s + 1) != EOF){
    tmp[0] = '!';
    int cnt = 0;
    int len = strlen(s + 1);
    for(int i = 1; i <= len; i++){
        tmp[++cnt] = '#';
        tmp[++cnt] = s[i];
    }
    tmp[++cnt] = '#';///cnt表示新数组tmp的大小（不包括第一个元素tmp[0]）
    int pos = 1, right = 2, f, e, index = 0;///很容易知道第一个元素的情况就直接枚举
    f = e = -1;///f、e是tmp数组下标映射到s数组的下标
    dp[0] = dp[1] = dp[cnt] = 1;
    ///right表示当前位置向右延伸的最长位置 + 1
    for(int i = 2; i < cnt ; i++){
        if(i < right) dp[i] = min(dp[2 * pos - i], right - i);
        else dp[i] = 1;
        while(tmp[i - dp[i]] == tmp[i + dp[i]]) dp[i]++;
        if(i + dp[i] > right){
            right = i + dp[i];
            pos = i;
        }
        if(dp[i] > 3 && dp[i] > dp[index]){
            f = (i - dp[i] + 2) / 2;
            e = (i + dp[i] - 2) / 2;
            ///这个自己画一下图就知道为什么了，这也就是为什么我把tmp数组从下标1开始记录#且s数组也是从下标1开始
            index = i;
        }
    }
    if(f < 0 || e < 0) {printf("No solution!\n"); continue;}
    printf("%d %d\n", f - 1, e - 1);
    for(int i = f; i <= e; i++){
        printf("%c", change(s[i], a[0]));
    }
    putchar('\n');
    }
    return 0;
}