回文串相关代码

main.cpp

bool is_palindrome(char *s, int n){
    int l = 0, r = n - 1;
    while(l < r){
        if(s[l] != s[r]) return false;
        ++l, --r;
    }
    return true;
}

manacher.cpp

/**
 * 不需要补`#`的写法
 * @param s 字符串
 * @param h0 偶回文串的回文半径
 * @param h1 奇回文串的回文半径
 * @param n 字符串长度
 */
void manacher(char *s, int *h0, int *h1, int n) { // s must be null-terminated
    //长度为奇数，i是中心点
    int r = 0, mid;
    for(int i = 0; i < n; i++) {
        int j = r > i ? min(h1[2*mid-i], r - i) : 0;
        while(j <= i && s[i-j] == s[i+j]) {
            ++j;
        }
        if(r < j + i) {
            r = j + i;
            mid = i;
        }
        h1[i] = j;
    }
    // 长度为偶数，i是后半部分的起点
    r = 0;
    for(int i = 0; i < n; i++) {
        int j = r > i ? min(h0[2*mid-i], r - i) : 0;

        while(j < i && s[i-j-1] == s[i+j]) {
            ++j;
        }
        if(r < j + i) {
            mid = i;
            r = j + i;
        }
        h0[i] = j;
    }
}