uva 12833 – daily potato

https://maguinta.github.io/https://maguinta.github.io/

Problem

找到迴文是起頭和結尾都是字符 c，並且 c 在中間出現 X 次

參考範例輸入，六個詢問 (a, 2) (b, 2) (c, 2) … 他把字符弄再一起，例如第一個 (a, 2) 來說，起頭為 a 且中間要出現恰好 2 次 a，主字串中只看到 abccba 和 aa。

Sample Input

1
2
3
4
5
6

1
8
abccbaab
6
abcabc
2 2 2 1 1 3

Sample Output

1
2
3
4
5
6
7

Case 1:
2
2
1
3
3
0

Solution

因為要恰好 X 個，對於每組詢問基本上只會有 n 個位置，當作起頭，然後 O(1) 檢查迴文即可。就算分 26 組下去，還是 TLE。

O(1) 檢查的方式按照 manacher’s algorithm 的做法，

manacher’s algorithm 算法核心，在 O(n) 時間內找到最長迴文子字串。

圖片與算法來源 here

可以將每組詢問壓到 O(log n) 以下，我們知道從每一個中心展開的最長迴文，也代表可以記錄展開的時候，恰好以某個字符開頭的最大總數。

對於每一組詢問，保證每一個中心最多當過一次迴文中心，因此只要總數大於等於指定個數，保證可以湊出來。

其 A[i][c] 表示以位置 i 為中心，起頭是字符 c，出現最多的 c 個數。之後問 c x 輸出有多少 A[i][c] >= x。

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

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXL 262144
char S[MAXL], C[MAXL], T[MAXL];
int dp[MAXL], n, m;
int A[MAXL][26], SUM[MAXL][26];
void exbuild(char S[]) { 
	n = strlen(S), m = 2 * n + 1;
    int mx = 0, idx = 0;
    int ans = 0;
	T[0] = '$', T[m] = '#', T[m + 1] = '