「UVA 11475」Extend to Palindrome「后缀数组」

这题算是经典题了，可以用$KMP/Manacher/SA$KMP/Manacher/SA做

这里丢上一个代码最长的做法：后缀数组

做法是将原串$s$s翻转得到$s'$s′,将$s'$s′接到$s$s后做$SA$SA

这样就会有一个很好的性质：我们可以快速求出以某个点或某两个点为中心的最长回文串长度。以$x$x为中心的答案为$\text{LCP}(\text{suffix}[x],\text{suffix}[x'])$LCP(suffix[x],suffix[x′])，$x'$x′为$x$x翻转后的位置

例如 $s=cabab,s'=babac$s=cabab,s′=babac

求以$s_4$s4​为中心的最长回文串长度

显然是$bab$bab，答案为$3$3，可以通过$\text{LCP}(\text{ab},\text{abac})=2$LCP(ab,abac)=2再$\times2+1$×2+1得到

长度偶数为偶数的回文串也是一样的求法.

现在再分析一下这题应该怎么补：在末尾找一个最长回文串，以这个回文串的中心为中心补全，这样显然需要补全的字符最少

最后提醒注意：求$\text{lcp}$lcp后一定要这个后缀的实际长度取$\min$min，或者$s$s与$s'$s′间加分隔符也行。

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define rep(i, j, k) for(int i = j; i <= k; ++ i)

namespace Suffix_Array {
	const int N = 4e5 + 5;
	char s[N], s1[N], s2[N], ch[N];
	int n, m, t[N], sa[N], rk[N], ht[N];
	int cnt[N], fir[N], sec[N];
	void buildsa() {
		rep(i, 1, n) ch[i] = s[i];
		sort(ch + 1, ch + n + 1);
		int l = unique(ch + 1, ch + n + 1) - (ch + 1);
		rep(i, 1, n) t[i] = lower_bound(ch + 1, ch + l + 1, s[i]) - ch;
		rep(i, 1, n) cnt[i] = 0;
		rep(i, 1, n) ++ cnt[t[i]];
		rep(i, 1, n) cnt[i] += cnt[i - 1];
		rep(i, 1, n) rk[i] = cnt[t[i] - 1] + 1;
		for(int k = 1; k <= n; k <<= 1) {
			rep(i, 1, n) fir[i] = rk[i];
			rep(i, 1, n) sec[i] = i + k > n ? 0 : rk[i + k];

			rep(i, 1, n) cnt[i] = 0;
			rep(i, 1, n) ++ cnt[sec[i]];
			rep(i, 1, n) cnt[i] += cnt[i - 1];
			rep(i, 1, n) t[n - -- cnt[sec[i]]] = i;

			rep(i, 1, n) cnt[i] = 0;
			rep(i, 1, n) ++ cnt[fir[i]];
			rep(i, 1, n) cnt[i] += cnt[i - 1];
			rep(i, 1, n) sa[cnt[fir[t[i]]] --] = t[i];

			bool dif = true; rk[sa[1]] = 1;
			rep(i, 2, n) {
				int & v = sa[i - 1], & u = sa[i];
				rk[u] = rk[v];
				if(fir[u] == fir[v] && sec[u] == sec[v]) dif = false;
				else ++ rk[u];
			}
			if(dif) break ;
		}
		for(int i = 1, k = 0; i <= n; i ++) {
			if(k) -- k;
			int j = sa[rk[i] - 1];
			for(; i + k <= n && j + k <= n && s[i + k] == s[j + k]; ++ k) ;
			ht[rk[i]] = k;
		}
	}
	int f[N][30], lg[N];
	void buildst() {
		lg[1] = 0;
		rep(i, 2, n) lg[i] = lg[i >> 1] + 1;
		rep(i, 1, n) f[i][0] = ht[i];
		for(int j = 1; (1 << j) <= n; ++ j)
			for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
				f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
	}
	int lcp(int a, int b) {
		a = rk[a]; b = rk[b];
		if(a > b) swap(a, b);
		++ a;
		int l = lg[b - a + 1];
		return min(f[a][l], f[b - (1 << l) + 1][l]);
	}
}
using namespace Suffix_Array;

//求以x(odd = 1)或x, x + 1(odd = 0)为中心的最长回文串长度 
int maxstr(int x, bool odd) {
	int y = odd ? n + 1 - x : n - x; //在后半部分对应点
	return lcp(x, y);
}

int main() {
	while(~ scanf("%s", s1 + 1)) {
		m = strlen(s1 + 1); n = m + m;
		rep(i, 1, m) s2[i] = s1[i];
		reverse(s2 + 1, s2 + m + 1);
		rep(i, 1, m) s[i] = s1[i];
		rep(i, 1, m) s[i + m] = s2[i];
		buildsa(); buildst();

		int pos = m + 1;
		rep(i, 1, m) {
			int r = m - i, w1 = maxstr(i, true), w2 = maxstr(i, false);
			w1 = min(w1, r + 1); w2 = min(w2, r + 1); //注意取min
			if(r + 1 == w1) pos = min(pos, i - r);
			if(i != m && r + 1 == w2) pos = min(pos, i - r + 1);
		}
		s[pos] = '\0';
		reverse(s + 1, s + pos);
		printf("%s%s\n", s1 + 1, s + 1);
	}
	return 0;
}