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
aaaa

Sample 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDU----(3294)Girls' research(manacher)

Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

2795
来自专栏ml

HDUOJ-----A == B ?

A == B ? Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

2876
来自专栏小樱的经验随笔

HDU 1000 A + B Problem(指针版)

A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

2724
来自专栏算法修养

HDU 5877 2016大连网络赛 Weak Pair(树状数组,线段树,动态开点,启发式合并,可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

37610
来自专栏小樱的经验随笔

POJ 2209 The King(简单贪心)

The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

2814
来自专栏小樱的经验随笔

POJ 1012 Joseph

Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53862 ...

3236
来自专栏ml

poj-------Common Subsequence(poj 1458)

Common Subsequence Time Limit: 1000MS Memory Limit: 10000K Total Submiss...

2905
来自专栏ml

HDUOJ----剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

35512
来自专栏算法修养

HOJ 2226&POJ2688 Cleaning Robot(BFS+TSP(状态压缩DP))

Cleaning Robot Time Limit: 1000MS Memory Limit: 65536K Total Submission...

2864
来自专栏ml

HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

3666

扫码关注云+社区

领取腾讯云代金券