Rockdu's Blog

【题目描述】

对于给定的字符串S，我们想知道它有多少个不同的回文子串。

【输入】

一行，一个长度不超过100000的仅小写字母构成的字符串。

【输出】

一个整数，代表不同的回文子串个数。

【输入样例】

abcd

【输出样例】

4

【提示】

有20%的数据，输入字符串的长度不超过1000。

本题有后缀数组的O(n log 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(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];
			len[now] = len[p] + 2;
			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", PLD::cnt - 1);
	return 0;
}