解題區/解題區 - UVa

UVa 12833 - Daily Potato

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

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[]) { // manacher's algorithm
    n = strlen(S), m = 2 * n + 1;
    int mx = 0, idx = 0;
    int ans = 0;
    T[0] = '$', T[m] = '#', T[m + 1] = '\0';
    for (int i = 0; i < n; i++)
    	T[i * 2 + 1] = '#', T[i * 2 + 2] = S[i];
    //
    memset(SUM[0], 0, sizeof(SUM[0]));
    for (int i = 1; i < m; i++) {
    	memcpy(SUM[i], SUM[i-1], sizeof(SUM[0]));
    	if ('a' <= T[i] && T[i] <= 'z')
    		SUM[i][T[i] - 'a']++;
    }
    //
    for (int i = 1; i < m; i++) {
        if (mx > i) {
        	memcpy(A[i], A[2 * idx - i], sizeof(A[2 * idx - i]));
            dp[i] = min(dp[2 * idx - i], mx - i);
            if (dp[2 * idx - i] >= mx - i) {
            	int r = idx - (mx - idx), l = 2 * idx - i - dp[2 * idx - i];
            	for (int j = 0; j < 26; j++) {
            		A[i][j] -= (SUM[r][j] - SUM[l][j]) * 2;
            	}
        	}
        } else {
        	for (int j = 0; j < 26; j++)
        		A[i][j] = SUM[i][j] - SUM[i-1][j];
            dp[i] = 1;
        }
        for(; T[i-dp[i]] == T[i+dp[i]]; dp[i]++)
        	if ('a' <= T[i+dp[i]] && T[i+dp[i]] <= 'z')
                A[i][T[i-dp[i]] - 'a'] += 2;
        if(dp[i] + i > mx)		mx = dp[i] + i, idx = i;
    }
//    for (int i = 1, j = 0; i < m; i ++, j++)
//    	printf("[%02d] %c %d\n", i, T[i], dp[i]);
}
vector<int> M[2][26];
void prepare() {
    for (int i = 0; i < 26; i++)
        M[0][i].clear(), M[1][i].clear();
    for (int i = 1; i < m; i++) {
//		printf("%c ", T[i]);
        for (int j = 0; j < 26; j++) {
            M[A[i][j]&1][j].push_back(A[i][j]);
//			printf("%d ", A[i][j]);
        }
//		puts("");
    }
    for (int i = 0; i < 26; i++) {
        sort(M[0][i].begin(), M[0][i].end());
        sort(M[1][i].begin(), M[1][i].end());
    }
}
void query(int x, char c) {
    if (x == 0)	{puts("0"); return;}
    int p = (int) (lower_bound(M[x&1][c - 'a'].begin(), M[x&1][c - 'a'].end(), x) - M[x&1][c - 'a'].begin());
    printf("%d\n", int(M[x&1][c - 'a'].size() - p));
}
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out2.txt", "w+t", stdout); 
    int testcase, N, Q, cases = 0;
    int x;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %s", &N, S);
        scanf("%d %s", &Q, C);
        exbuild(S);
        prepare();
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < Q; i++) {
            scanf("%d", &x);
            query(x, C[i]);
        }
    }
    return 0;
}
/*
1
8
abccbaab
6
abcabc
2 2 2 1 1 3
1000
6
abaaba
7
aaaaaab
5 4 3 2 1 0 2
123
10
ccecabebcb
10
ebddcdacad
5 6 2 5 5 5 5 1 9 9
10
abbbbeaaba
10
cbabcabcec
2 0 1 8 5 6 2 4 8 1
10
baddaeaecb
10
bbdebdbedd
1 5 5 6 2 9 9 1 5 0
*/