The Number of Palindromes

time limit per test 1 second memory limit per test 256 megabytes
Now, you are given a string S. We want to know how many distinct substring of S which is palindrome.

传送门:HDU3948

Input

The first line of the input contains a single integer T(T<=20), which indicates number of test cases.
Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.

Output

For every test case, you should output “Case #k:” first in a single line, where k indicates the case number and starts at 1. Then output the number of distinct substring of S which is palindrome.

Sample Input

1
2
3
4
3
aaaa
abab
abcd

Sample Output

1
2
3
Case #1: 4
Case #2: 4
Case #3: 4

题解

题意:求一个串中不同的回文串个数
马拉车加后缀数组并去重

AC code:(不包含输入类)

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
import java.io.*;
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
SA sa=new SA();
Manacher m=new Manacher();
int t=sc.nextInt();
int count=0;
while(sc.hasNext()){
String s=sc.next();
count++;
long sum=0;
m.makep(s);
sa.getSA(m.ns,m.count);
sa.getHeight(m.ns,m.count);
int temp=0;
for(int i=1;i<=m.count;i++){
int x=sa.sa[i];
temp=Math.min(temp, sa.height[i]); //很重要
if(m.p[x]<=temp)continue;
sum+=(m.p[x]-temp)/2;
temp=m.p[x];
}
pw.print("Case #"+count+": ");
pw.println(sum);
pw.flush();
}
}
}
class SA{
/*【倍增算法O(nlgn)】待排序的字符串放在r 数组中,从r[0]到r[n-1],长度为n,且最大值小于m
使用倍增算法前,需要保证r数组的值均大于0。然后要在原字符串后添加一个0号字符
所以,若原串的长度为n,则实际要进行后缀数组构建的r数组的长度应该为n+1.所以调用da函数时,对应的n应为n+1.
【使用说明】:字符串从0下标开始,算法最后要加上一个0,sa的值是0~n-1(下标为1~n),rank的值是1~n(下标是0~n-1),height下标从0开始,但是
height[0]=0,height[1]=0,height[2]才表示与前一个的最长公共前缀。
相当于height下标为2-n
*/
int maxn=200005;
int[]sa,wa,wb,ws,wv;
int[]rank;
int[]height;
int[]r;
int[][]dp;
int n;
int m;
SA(){
sa=new int[maxn];
wa=new int[maxn];
wb=new int[maxn];
ws=new int[maxn];
wv=new int[maxn];
height=new int[maxn];
rank=new int[maxn];
r=new int[maxn];
//dp=new int[maxn][20];
}

boolean cmp(int[]f,int x,int y,int w){
return f[x] == f[y] && f[x + w] == f[y + w];
}

void getSA(String s){
n=s.length();
for(int i=0;i<s.length();i++){
r[i]=s.charAt(i);
}
r[n]=0;
da(r,sa,s.length()+1,256);
}
void getSA(int[]s,int n){
s[n]=0;
da(s,sa,n+1,256);
}
void getHeight(int[]s,int k){
calheight(s,sa,k);
}

void da(int[] r, int sa[], int n, int m){
int i, j, p;
int[]x = wa;
int[]y = wb;
int[]temp;
for (i = 0; i < m; ++i) ws[i] = 0;
for (i = 0; i < n; ++i) ws[x[i]=r[i]]++;
for (i = 1; i < m; ++i) ws[i] += ws[i-1];
for (i = n-1; i >= 0; --i) sa[--ws[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p){
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++]=sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) ws[i] = 0;
for (i = 0; i < n; ++i) ws[wv[i]]++;
for (i = 1; i < m; ++i) ws[i] += ws[i-1];
for (i = n-1; i >= 0; --i) sa[--ws[wv[i]]] = y[i];
for (temp=x,x=y,y=temp, p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? (p-1) : p++;
}
}

void calheight(int[] r, int sa[], int n){
int i, j, k = 0;
for (i = 1; i <= n; ++i) rank[sa[i]] = i;
for (i = 0; i < n; height[rank[i++]] = k){
if(k>0)k--;
for (j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);
}
}
}

class Manacher{
int maxn=200050;//2倍字符串长度
int[]p;
//char[]ns;
int[]ns;
int maxlen;
int maxpoint;
int start;
int end;
int count;
Manacher(){
p=new int[maxn];
//ns=new char[maxn];
ns=new int [maxn];
}
/*p[i]表示以i为中心在新字符串中最长的回文子串半径 p[i]-1是真实的回文子串长度
* maxlen-1是最长回文子串长度*/
void makep(String s){
ns[0]='$';ns[1]='#';
start=-1;
end=-1;
count=2;
for(int i=0;i<s.length();i++){
ns[count++]=s.charAt(i);
ns[count++]='#';
}
maxlen=0;
maxpoint=0;
int mx=0;
int id=0;
for(int i=1;i<count;i++){
p[i]=mx>i?Math.min(p[2*id-i], mx-i):1;//只有当mx>i且p[2*id-i]<mx-i时p[i]=p[2*id-i] 其他还需要在下面的while继续匹配
while(i-p[i]>=0&&i+p[i]<count&&ns[i+p[i]]==ns[i-p[i]])++p[i];
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
if(maxlen<p[i]){
maxlen=p[i];
maxpoint=i;
}
}
}
}