比赛 20160414 评测结果 AAAAAAAAAA
题目名称 随机数消除器 最终得分 100
用户昵称 Fmuckss 运行时间 1.270 s
代码语言 C++ 内存使用 353.17 MiB
提交时间 2016-04-14 16:37:53
显示代码纯文本
#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; 
}