URAL 1297 後綴數組求最長回文子串 - 含特殊情況處理

問題描述

給定字符串 S，求其最長回文子串。若有多個長度相同，輸出字典序最小（或最早出現）的。多組測試數據。

後綴數組 + LCP 方法

構造字符串 T = S + '#' + reverse(S)。對 T 構建後綴數組 SA 和高度數組 Height。最長公共前綴對應原串中的回文。需注意：回文中心在 S 和 reverse(S) 的對應位置。遍歷 Height，若相鄰後綴一個來自 S，一個來自 reverse(S)，且它們的起始位置滿足 SA[i] + SA[i-1] == |T| - Height[i]（保證對稱），則 Height[i] 為回文長度候選。取最大長度，若長度相同取字典序最小（即起始位置最小）。

特殊情況處理

對於 ABCDEFDCBA 這類回文，普通 LCP 可能匹配到非對稱的公共前綴。需額外檢查 SA[i] + SA[i-1] == n - Height[i] 條件（n = |T|），確保是真正的回文對稱。

複雜度

後綴數組構建 O(n log n)（倍增/基數排序），LCP O(n)，總 O(n log n)，n ≤ 4000 極快。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4010;

int sa[MAXN], rk[MAXN], tmp[MAXN], h[MAXN];
char str[MAXN];
int n;

bool cmp_sa(int i, int j, int k) {
    if (rk[i] != rk[j]) return rk[i] < rk[j];
    int ri = i+k <= n ? rk[i+k] : -1;
    int rj = j+k <= n ? rk[j+k] : -1;
    return ri < rj;
}

void build_sa() {
    for (int i = 0; i <= n; ++i) { sa[i] = i; rk[i] = i < n ? str[i] : -1; }
    for (int k = 1; k <= n; k <<= 1) {
        sort(sa, sa+n+1, [&](int i, int j){ return cmp_sa(i,j,k); });
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; ++i)
            tmp[sa[i]] = tmp[sa[i-1]] + cmp_sa(sa[i-1], sa[i], k);
        for (int i = 0; i <= n; ++i) rk[i] = tmp[i];
        if (rk[sa[n]] == n) break;
    }
}

void build_lcp() {
    for (int i = 0; i <= n; ++i) rk[sa[i]] = i;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (rk[i] == 0) { h[0] = 0; continue; }
        int j = sa[rk[i]-1];
        while (i+k < n && j+k < n && str[i+k] == str[j+k]) ++k;
        h[rk[i]] = k;
        if (k) --k;
    }
}

int main() {
    while (scanf("%s", str) == 1) {
        string s(str);
        string rev = s; reverse(rev.begin(), rev.end());
        string t = s + "#" + rev;
        n = t.size();
        for (int i = 0; i < n; ++i) str[i] = t[i];
        str[n] = 0;
        build_sa();
        build_lcp();
        int bestLen = 0, bestPos = 0;
        int split = s.size();
        for (int i = 1; i <= n; ++i) {
            int a = sa[i], b = sa[i-1];
            if ((a < split) == (b < split)) continue; // 必須一邊在 S，一邊在 rev(S)
            if (a + b != n - h[i]) continue; // 對稱條件
            if (h[i] > bestLen || (h[i] == bestLen && min(a,b) < bestPos)) {
                bestLen = h[i];
                bestPos = min(a,b);
            }
        }
        if (bestLen == 0) printf("%c\n", s[0]);
        else printf("%s\n", s.substr(bestPos, bestLen).c_str());
    }
    return 0;
}