首页 > 代码库 > ural 1960 Palindromes and Super Abilities

ural 1960 Palindromes and Super Abilities

题意:找出s[1..x]的本质不同的回文串的个数

分析:回文树模板题

/************************************************Author        :DarkTongCreated Time  :2016年09月21日 星期三 21时17分07秒File Name     :a.cpp *************************************************/#include <bits/stdc++.h>using namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int maxn = 100000 + 10;const int N = 26;struct Palindromic_Tree{	int next[maxn][N];	int fail[maxn];	int cnt[maxn];	int num[maxn];	int len[maxn];	int S[maxn];	int last;	int n;	int p;	int ans[maxn];	int newNode(int l)	{		for(int i=0;i<N;++i) next[p][i]=0;		cnt[p] = 0;		num[p] = 0;		len[p] = l;		return p ++;	}	void init()	{		p = 0;		newNode(0);		newNode(-1);		last = 0;		n = 0;		S[n] = -1;		fail[0] = 1;		ans[0] = 0;	}	int get_fail(int x)	{		while(S[n - len[x] - 1] != S[n]) x = fail[x];		return x;	}	void add(int c)	{		c -= ‘a‘;		S[++ n] = c;		int cur = get_fail(last);		if(!next[cur][c])		{			int now = newNode(len[cur] + 2);			fail[now] = next[get_fail(fail[cur])][c];			next[cur][c] = now;			num[now] = num[fail[now]] + 1;			ans[n] = ans[n-1] + 1;		}		else ans[n] = ans[n-1];		last = next[cur][c];		cnt[last] ++;	}	void count()	{		for(int i=p-1;i>=0;--i) cnt[fail[i]] += cnt[i];	}	void solve(char *s)	{		int cur = 0;		int n = strlen(s+1);		for(int i=1; i<=n ; ++i)		{			cur = next[cur][s[i]-‘a‘];			printf("%d%c", cnt[i], i==n ? ‘\n‘ : ‘ ‘);		}	}}plt;char s[maxn];int main(){	int T, cas=1;	scanf("%s", s+1);	plt.init();	for(int i=1; s[i] ; ++ i) 		plt.add(s[i]);	//	plt.count();	//	plt.solve(s);	int n = strlen(s+1);	for(int i=1;i<=n;++i) printf("%d%c", plt.ans[i], i==n ? ‘\n‘ : ‘ ‘);	return 0;}

  

ural 1960 Palindromes and Super Abilities