专栏首页算法修养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
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 条评论
登录 后参与评论

相关文章

  • HDU 5618 Jam's problem again(三维偏序,CDQ分治,树状数组,线段树)

    Jam's problem again Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 655...

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • LeetCode Contest 166

    但是在用c++的快排的时候,被坑了,我一直的习惯是写自定义比较函数,没有写运算符重载,不知道为什么一直RE,浪费了挺多时间

    ShenduCC
  • Codeforces Round #536 (Div. 2) D. Lunar New Year and a Wander(bfs)

    题目链接:http://codeforces.com/contest/1106/problem/D

    Ch_Zaqdt
  • 算法系列 图数据结构探索(无向图搜索)

    算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第10篇《无向图搜索》,非常赞!希望对大家有帮助,大家会喜欢!

    大数据和云计算技术
  • 【 HDU - 4456 】Crowd (二维树状数组、cdq分治)

    给你一个n行n列的格子,一开始每个格子值都是0。有M个操作,p=1为第一种操作,给格子(x,y)增加z。p=2为询问与格子(x,y)的曼哈顿距离不超过z的格子值...

    饶文津
  • BZOJ 1083: [SCOI2005]繁忙的都市【Kruscal最小生成树裸题】

    1083: [SCOI2005]繁忙的都市 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2925  Sol...

    Angel_Kitty
  • POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)

    Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1057...

    Angel_Kitty
  • HDU 1878 欧拉回路

    #include <bits/stdc++.h> using namespace std; const int N=1005; int in[N]; i...

    用户2965768
  • hdu---(1280)前m大的数(计数排序)

    前m大的数 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

    Gxjun

扫码关注云+社区

领取腾讯云代金券