记录编号	250599	评测结果	AAAAAAAAAA
题目名称	随机数消除器	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	1.242 s
提交时间	2016-04-15 13:58:45	内存使用	353.17 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e7;

class pm {
private:
	struct node {
		int son[5];
		int fa;
	}ns[maxn];
	int fail[maxn];
	int len[maxn];
	char s[maxn];
	int cnt[maxn];
	int ans;
	int now;
public:
	pm() { len[1] = -1, fail[0] = 1, now = 2; }
	
	inline int get_fail(int i, int f) {
		while(s[i-len[f]-1] != s[i]) f = fail[f];//如果上一个匹配位不能匹配，那就找上上一个匹配位
		return f; 
	}
	
	void read() {
		scanf("%s", s+1);
	}
	
	void build() {
		int cur;
		int last = 0;
		int ch;
		for(int i = 1; s[i]; i++) {
			cur = get_fail(i, last);//保证一定能找到一个失配的 
			ch = s[i] - 'a' + 1;
			if(!ns[cur].son[ch]) {
				now++;
				len[now] = len[cur]+2;
				fail[now] = ns[get_fail(i, fail[cur])].son[ch];//找到上次能匹配的
				ns[cur].son[ch] = now; 
			}
			last = ns[cur].son[ch];
			cnt[last]++;
		} 
	}
	
	void out() {
		for(int i = 1; i <= now; i++) {
			if(cnt[i]) ans++;
		}
		printf("%d\n", ans);
	}
}solver;

int main() {
	freopen("randomb.in", "r", stdin);
	freopen("randomb.out", "w", stdout); 
	solver.read();
	solver.build();
	solver.out();
	return 0; 
}