HDU 5157 Harry and magic string(回文树)
HDU 5157 Harry and magic string(回文树)
Harry and magic string
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 223 Accepted Submission(s): 110
Problem Description
Harry got a string T, he wanted to know the number of T’s disjoint palindrome substring pairs. A string is considered to be palindrome if and only if it reads the same backward or forward. For two substrings of (where a1 is the beginning index of is the ending index of x. as the same of y), if both x and y are palindromes and then we consider (x, y) to be a disjoint palindrome substring pair of T.
Input
There are several cases. For each test case, there is a string T in the first line, which is composed by lowercase characters. The length of T is in the range of [1,100000].
Output
For each test case, output one number in a line, indecates the answer.
Sample Input
aca
aaaaSample Output
3
15求一个字符串中所有不相交的回文串对回文树，先倒着扫一遍，再正着扫一遍#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
typedef long long int LL;
const int MAX=1e5+5;
char str[MAX];
struct Tree
{
int next[MAX][26];
int fail[MAX];
LL num[MAX];
int len[MAX];
int s[MAX];
int last;
int n;
int p;
int new_node(int x)
{
memset(next[p],0,sizeof(next[p]));
num[p]=0;
len[p]=x;
return p++;
}
void init()
{
p=0;
new_node(0);
new_node(-1);
last=0;
n=0;
s[0]=-1;
fail[0]=1;
}
int get_fail(int x)
{
while(s[n-len[x]-1]!=s[n])
x=fail[x];
return x;
}
LL add(int x)
{
x-='a';
s[++n]=x;
int cur=get_fail(last);
if(!(last=next[cur][x]))
{
int now=new_node(len[cur]+2);
fail[now]=next[get_fail(fail[cur])][x];
next[cur][x]=now;
num[now]=num[fail[now]]+1;
last=now;
}
return num[last];
}
}tree;
LL sum[MAX];
int main()
{
while(scanf("%s",str)!=EOF)
{
int len=strlen(str);
sum[len]=0;
tree.init();
for(int i=len-1;i>=0;i--)
{
sum[i]=sum[i+1]+tree.add(str[i]);
}
tree.init();
LL ans=0;
for(int i=0;i<len;i++)
{
ans+=(LL)tree.add(str[i])*sum[i+1];
}
printf("%lld\n",ans);
}
return 0;
}