题目传送门:http://acm.timus.ru/problem.aspx?space=1&num=1960
PAM板题,一个节点就是一个本质不同的字符串
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int MAXN = 100000+9; char pat[MAXN]; namespace Palindromic_Tree{ #define PAM Palindromic_Tree #define SIGMA_SIZE 26 int ch[MAXN][SIGMA_SIZE],len[MAXN]; int fail[MAXN],last,cnt; inline void extend(int pos, int c){ int w = last; while (pat[pos-len[w]-1] != pat[pos]) w = fail[w]; if (!ch[w]){ int nw = ++cnt, k=fail[w]; len[nw] = len[w]+2; while (pat[pos-len[k]-1] != pat[pos]) k = fail[k]; fail[nw] = ch[k]; ch[w] = nw; } last = ch[w]; } inline void build(char *s){ fail[0] = fail[1] = 1; last = 1; cnt = 1; len[1] = -1; int n = strlen(s+1); for (int i=1;i<=n;i++) extend(i,s[i]-'a'), printf("%d ",cnt-1); } }; int main(){ scanf("%s",pat+1); PAM::build(pat); return 0; }
The following time I learn a weblog, I hope that it doesnt disappoint me as much as this one. I imply, I know it was my option to learn, but I actually thought youd have something attention-grabbing to say. All I hear is a bunch of whining about one thing that you might repair if you happen to werent too busy searching for attention.
I am often to blogging and i really appreciate your content. The article has really peaks my interest. I am going to bookmark your site and keep checking for new information.