最長回文子串 HDU3068 POJ3974 CF.7D

這有篇寫的很好的文章：Manacher's ALGORITHM: O(n)時間求字符串的最長回文子串

模板：

// t為處理過的字符串，p為記錄長度的數組
memset(p, 0, sizeof(p));
// mx為已判斷回文串最右邊位置，id為中間位置，mmax記錄p數組中最大值
int mx = 0, id = 0, mmax = 0;
for (int i = 1; t[i]; i++) {
	p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
	while (t[i + p[i]] == t[i - p[i]])
		p[i]++;
	if (i + p[i] > mx) {
		mx = i + p[i];
		id = i;
	}
	if (mmax < p[i]) 
		mmax = p[i];
}
// 最長為mmax - 1

基礎題：
HDU 3068 最長回文：Solution code
POJ 3974 Palindrome：Solution code

Codeforces Beta Round #7 D. Palindrome Degree

題目地址

題意：
規定一個長度為n的字符串是k-回文為：長度n/2的前綴和後綴是(k-1)-回文，k為回文的度。比如abacaba是3。
給出一個由數字和字母組成的字符串，長度<=5*10^6，大小敏感，求所有前綴的回文度。

分析：
這題折騰了一下午...
利用Mnancher算法求出的p數組來進行判斷。
研究frog姐的題解研究半天，無法想象她那算法是怎麼想出來的orz，然後有看了某大神的dp算法，最後看了一個git上的算法，結果人家用的Manacher算法不一般，不過看了他的思路後，我茅塞頓開.....

開一個數組k，如果前i個是回文，就在它的中心標記為1，然後循環向後找出符合k[i]&&k[(i+1)/2]位置，也就是本身是前綴回文，而且它的前綴(i-1)/2也是前綴回文，那讓k[i]=k[(i+1)/2]+1就行了。

果然還是太弱。

CODE

總結：
對於字符串可以考慮遞推、dp、以及yy。

UPDATE：
後來研究了一下前面幾個算法，發現frog姐的還是很神，所謂的dp其實跟我想的差不多。