回文相关

求最长回文串：回文子串的最大长度

AC 代码：(字符串 hash 解决)

#include <bits/stdc++.h>

using ULL = unsigned long long;
constexpr int P = 131;
char s[2000010];
ULL h1[2000010], h2[2000010], p[2000010];
int res;
void solve() {
    int n = strlen(s + 1) * 2;
    for (int i = n; i; i -= 2) {
        s[i] = s[i / 2];
        s[i - 1] = 'z' + 1;
    }
    s[++n] = 'z' + 1;

    for (int i = 1; i <= n; ++i) {
        h1[i] = h1[i - 1] * P + s[i] - 'a' + 1;
    }
    h2[n + 1] = 0;  // 防止上个样例影响这次运算
    for (int i = n; i; --i) {
        h2[i] = h2[i + 1] * P + s[i] - 'a' + 1;
    }
    p[0] = 1;
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * P;
    }

    auto cal1 = [&](int l, int r) -> ULL {  // 计算 h1 哈希
        return h1[r] - h1[l - 1] * p[r - l + 1];
    };
    auto cal2 = [&](int l, int r) -> ULL {  // 计算 h2 哈希
        return h2[l] - h2[r + 1] * p[r - l + 1];
    };

    for (int i = 1; i <= n; ++i) {
        int r = std::min(i - 1, n - i);
        if (res >= r || cal1(i - res, i - 1) != cal2(i + 1, i + res)) {
            continue;
        }
        while (res <= r && cal1(i - res, i - 1) == cal2(i + 1, i + res)) {
            res++;
        }
        res--;
    }
}
int main() {
    for (int T = 1; ; ++T) {
        res = 1;
        scanf("%s", s + 1);
        if (strcmp(s + 1, "END")) {
            solve();
            printf("Case %d: %d\n", T, res);
        } else {
            break;
        }
    }

    return 0;
}

回文子序列：密码脱落

AC 代码：

#include <bits/stdc++.h>

int main() {
    std::string s;
    std::cin >> s;
    int n = s.size();
    s = " " + s;

    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        dp[i][i] = 1;
    }
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = std::max(dp[l + 1][r], dp[l][r - 1]);
            if (s[l] == s[r]) {
                dp[l][r] = dp[l + 1][r - 1] + 2;
            }
        }
    }
    std::cout << n - dp[1][n] << '\n';

    return 0;
}

树上求最长回文子序列：Hossam and (sub-)palindromic tree
AC 代码：