manacher-algorithm

發表於 更新於 Disqus：

教學有空補
目前只有模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int manacher(string s) { //return max palindrome substring length in O(|S|)
	int n = 2 * s.size() + 1, ans = 0;
	string t(n, 0);//new string
	vector<int> len(n);//len[i]: max length when mid at i
	for(int i = 0; i < n; i++) {
		if(i & 1)
			t[i] = s[i / 2];
	}
	for(int i = 0, l = 0, r = -1; i < n; i++) {
		len[i] = (i <= r ? min(len[2 * l - i], r - i) : 0);
		while(i - len[i] >= 0 && i + len[i] < n && t[i - len[i]] == t[i + len[i]])
			len[i]++;
		len[i]--;
		ans = max(ans, len[i]);
		if(i + len[i] > r)
			l = i, r = i + len[i];
	}
	return ans;
}

練習題