【Ural 1960】Palindromes and Super Abilities

题目传送门：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;
}