Rockdu's Blog

Input输入Str（Str的长度 <= 100000)Output输出最长回文子串的长度L。Sample Input

daabaac

Sample Output

5

一个标准的Manacher，可以看看这篇博客，讲的很清楚：我就是“博客”。另外突然发现max，min好慢啊，而且其中的两种情况可以合并。附代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int RL[maxn << 1], cnt, mx;
char s[maxn << 1], r[maxn];

void Manacher() {
	int Mr = 0, Mpos = 0;
	int len = cnt;
	for(register int i = 0; i < len; ++i) {
		RL[i] = min(RL[(Mpos << 1) - i], Mr - i);
		for(; i - RL[i] >= 0 && i + RL[i] <= len && s[i - RL[i]] == s[i + RL[i]]; ++RL[i]);
		--RL[i];
		if(Mr < RL[i] + i) Mr = i + RL[i], Mpos = i;
		mx = max(mx, RL[i]);
	}
}

int main() {
		scanf("%s", r);
		int mxr = strlen(r);
		for(register int i = 0; i < mxr; ++i)
			{s[cnt++] = '#', s[cnt++] = r[i];}
		s[cnt++] = '#';
		Manacher();
		printf("%d\n", mx);
	return 0;
}

 今天刚刚学了回文自动机，又写了一遍，充分证实了Manacher的复杂度是O(n)的并且回文自动机常数的确巨小。下面一个板子

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int mx;

namespace PLD {
	char s[maxn];
	int trie[maxn][26], num, arr[maxn], sum[maxn], fail[maxn], len[maxn];
	int cnt, last, pos;
	void init() {
		cnt = 1, last = 0;
		len[0] = 0, len[1] = -1;
		fail[0] = 1, pos = 0;
	}
	int getfail(int p) {
		while(p != 1 && s[pos - len[p] - 1] != s[pos])
			p = fail[p];
		return p;
	}
	void add(int x) {
		int id = s[x] - 'a';
		int p = getfail(last);
		if(!trie[p][id]) {
			int now = ++cnt;
			fail[now] = trie[getfail(fail[p])][id];
			mx = max(len[now] = len[p] + 2, mx);
			trie[p][id] = now;
		}
		last = trie[p][id];
		++sum[last];
	}
	void push_up() {
		for(register int i = cnt; i >= 2; --i)
			sum[fail[i]] += sum[i];
	}
	void create() {
		int len = strlen(s);
		for(register int i = 0; i < len; ++i) 
			pos = i, add(i);
		push_up();
	}
}

int main() {
	PLD::init();
	scanf("%s", PLD::s);
	PLD::create();
	printf("%d", mx);
	return 0;
}