HDU5658 CA Loves Palindromic(回文树)

描述

传送门:我是传送门

CA loves strings, especially loves the palindrome strings. One day he gets a string, he wants to know how many palindromic substrings in the substring $S[l,r]$. Attantion, each same palindromic substring can only be counted once.

输入

First line contains $T$ denoting the number of testcases. $T$ testcases follow. For each testcase: First line contains a string $S$. We ensure that it is contains only with lower case letters. Second line contains a interger $Q$, denoting the number of queries. Then $Q$ lines follow, In each line there are two intergers $l,r$, denoting the substring which is queried. $1≤T≤10$, $1≤length≤1000, 1≤Q≤100000, 1≤l≤r≤length$

输出

For each testcase, output the answer in $Q$ lines.

样例

输入

1
abba
2
1 2
1 3

输出

2
3

Note

In first query, the palindromic substrings in the substring $S[1,2]$ are “a”,”b”.
In second query, the palindromic substrings in the substring $S[1,2]$ are “a”,”b”,”bb”.
Note that the substring “b” appears twice, but only be counted once.
You may need an input-output optimization.

思路

利用回文树的性质暴力预处理所有子串

每次查询都是$0(1)$的复杂度

$ 不同回文子串的数量 = P - 2 $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/*
* =========================================================================
*
* Filename: C.cpp
*
* Link: http://acm.hdu.edu.cn/showproblem.php?pid=5658
*
* Version: 1.0
* Created: 2018/09/03 04时11分41秒
* Revision: none
* Compiler: g++
*
* Author: 杜宁元 (https://duny31030.top/), duny31030@126.com
* Organization: QLU_浪在ACM
*
* =========================================================================
*/
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define pre(i,a,n) for(int i=a;i>=n;i--)
#define ll long long
#define max3(a,b,c) fmax(a,fmax(b,c))
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int MAXN = 1e5+10;
const int N = 26;
char s[MAXN];
struct node
{
int next[N]; // next指针,next指针和字典树类似,指向的串为
// 当前穿两端加上同一个字符构成
int fail; // fail指针,失配后跳转到fail指针指向的节点
int cnt; // 表示节点i的本质不同的串的个数
// 建树时求出的不是完全的,最后Count()函数跑一遍以后才是正确的
int num; // 表示以节点i表示的最长回文串的最右端点为回文串结尾的回文个数
int len; // 表示以当前节点表示的最长回文串长度(一个节点表示一个回文串)
int S; // 存放添加的字符
}pam[MAXN];
int last; // 指向新添加一个字母后所形成的最长回文串表示的节点
int n; // 表示添加的字符个数
int p; // 表示添加的节点个数

int newnode(int x)
{
for(int i = 0;i < N;i++)
pam[p].next[i] = 0;
pam[p].cnt = 0;
pam[p].num = 0;
pam[p].len = x;
return p++;
}

void Init()
{
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
pam[n].S = -1; // 开头存放一个字符集中没有的字符,减少特判
pam[0].fail = 1;
}

int get_fail(int x)
{
while(pam[n-pam[x].len-1].S != pam[n].S)
x = pam[x].fail;
return x;
}

void Add(int c)
{
c -= 'a';
pam[++n].S = c;
int cur = get_fail(last); // 通过上一个回文串找这个回文串的匹配位置
if(!pam[cur].next[c]) // 如果这个回文串没有出现过,说明出现了
// 一个新的本子不同的回文串
{
int now = newnode(pam[cur].len+2); // 新建节点
pam[now].fail = pam[get_fail(pam[cur].fail)].next[c];
// 和AC自动机一样建立fil指针,以便失败后回跳
pam[cur].next[c] = now;
pam[now].num = pam[pam[now].fail].num+1;
}
last = pam[cur].next[c];
pam[last].cnt++;
}

void Count()
{
for(int i = p-1;i >= 0;--i)
{
pam[pam[i].fail].cnt += pam[i].cnt;
// 父亲累加儿子才cnt,因为如果fail[v] = u , 则u一定是v的子回文串
}
}
int T,que,l,r;
int main()
{
ios
#ifdef ONLINE_JUDGE
#else
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
int pr[1010][1010];
memset(pr,0,sizeof pr);
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int len = strlen(s);
for(int i = 0;i < len;i++)
{
Init();
for(int j = i;j < len;j++)
{
Add(s[j]);
pr[i][j] = p-2;
}
}
scanf("%d",&que);
while(que--)
{
scanf("%d %d",&l,&r);
printf("%d\n",pr[l-1][r-1]);
}
}
fclose(stdin);
// fclose(stdout);
return 0;
}