回文树根据以下博客学的,写得很好
传送门:http://blog.csdn.net/u013368721/article/details/42100363
After solving seven problems on Timus Online Judge with a word “palindrome” in the problem name, Misha has got an unusual ability. Now, when he reads a word, he can mentally count the number of unique nonempty substrings of this word that are palindromes.
Dima wants to test Misha’s new ability. He adds letters s 1, ..., s n to a word, letter by letter, and after every letter asks Misha, how many different nonempty palindromes current word contains as substrings. Which n numbers will Misha say, if he will never be wrong?
Input
The only line of input contains the string s 1... s n, where s i are small English letters (1 ≤ n ≤ 10 5).
Output
Output n numbers separated by whitespaces, i-th of these numbers must be the number of different nonempty substrings of prefix s 1... s i that are palindromes.
Sample
input | output |
---|---|
aba | 1 2 3 |
题意:大概就是每个前缀有多少种回文串
思路:如果看懂了回文树,就会知道没当开新结点证明出现了新的回文串。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 100080
#define N 26
char str[maxn];
struct Palidromic_Tree
{
int next[maxn][N];//next指针,和字典树类似,指向的串为当前串两端加上同一个字符构成。
int fail[maxn];//fail指针,失配后跳转到fail指针指向的节点
int cnt[maxn];
int num[maxn];
int len[maxn]; //len[i]表示节点i表示的回文串的长度
int S[maxn]; //存放添加的字符
int last; //指向上一个字符所在的节点,方便下一次add
int n; //字符数组指针
int p; //节点指针
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;
}
int get_fail( int x )//和KMP一样,适配后找一个尽量最长的
{
while( S[n - len[x] - 1] != S[n] ) x = fail[x];
return x;
}
void add( int c )
{
c -= 'a';
S[++n] = c;
//printf("S[%d]=:%d\n",n,S[n]);
int cur = get_fail( last );//通过上一个回文串找这个回文串的匹配位置
//printf("cur=%d\n",cur);
if( !next[cur][c] )//如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串
{
int now = newnode( len[cur] + 2 );//新建节点
//printf("now=%d\n",now);
fail[now] = next[get_fail(fail[cur])][c];//和AC自动机一样建立fail指针,以便适配后跳转
//printf("fail[now]=%d\n",fail[now]);
next[cur][c] = now;
//printf("next[%d][%d]=%d\n",cur,c,now);
num[now] = num[fail[now]] + 1;
//printf("num[%d]=%d\n",now,num[now]);
}
last = next[cur][c];
//printf("last=%d\n",next[cur][c]);
cnt[last]++;
//printf("cnt[last]=%d\n",cnt[last]);
}
void count()
{
for(int i = p-1;i >= 0;--i) cnt[fail[i]] += cnt[i];
//父亲累加儿子的cnt,因为如果fail[v]=u,则u一定是v的子回文串
}
}pt;
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
pt.init();
scanf("%s",str);
int len = strlen(str);
//printf("%s",str);
for(int i = 0;i < len;i++)
{
//for(int j = 0;j < 3;j++) puts("");
pt.add(str[i]);
printf("%d",pt.p-2);
if(i == len-1) puts("");
else printf(" ");
}
return 0;
}
版权声明:本文为a305657原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。