解題區/出題解題

[ACM 題目] 動態前綴

contents

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

Problem

某 M 「給一個字串 S，接著詢問操作 [l, r] 告訴區間內是否剛好為一個迴文？」
學弟 「用最長迴文的方式去想嗎？」
某 M 「我沒有標準答案哦 wwww，吾等還在想能不能離線 O(1)。」

暗自敲著 UVa 另外一題類似題說著，就算能 O(1) 檢查迴文，區間還是要窮舉 O(n)，在此宣告某 M 陣亡－ Time Limit 。

某 M 心想，假解也是不錯選擇，單純詢問迴文肯定會被 manacher’s algorithm 秒掉 (O(1) - O(n))。如果詢問 [l, r] 的子字串是否符合 pattern AA (例如 abcabc，其中 A = abc)，也會被 suffix array、suffix tree 解決 (O(log n) - O(n log n)/O(n))。

百般無奈之下，也許這題就這樣定好了：

C p x：將字串位置 p 修改成字符 x。
Q p q：求子字串 S.substr(p) 和 S.substr(q) 的最長共同前綴長度。

1
2
3
4
5
6
7
8
void change(char s[], int p, int x) {
    s[p] = x;
}
int query(char s[], int p, int q) {
    int ret = 0;
    for (; s[p] == s[q] && s[p] && s[q]; p++, q++, ret++);
    return ret;
}

Sample Input

1
2
3
4
5
abcdabcc
3
Q 0 4
C 3 c
Q 0 4

Sample Output

1
2
3
4

Solution

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const long long mod = 100000007LL;
#define MAXN (1<<17)
char S[MAXN];
long long base[MAXN];
long long tree[MAXN<<1];
long long build(int k, int l, int r) {
    assert(l <= r);
    if (l == r)
        return tree[k] = (S[l] % mod);
    int m = (l + r)/2;
    build(k<<1, l, m);
    build(k<<1|1, m+1, r);
    tree[k] = (tree[k<<1] * base[r - m] + tree[k<<1|1]) %mod;
}
void modify(int k, int l, int r, int x, int v) {
    if (l == r) {
        tree[k] = v;
        return;
    }
    int m = (l + r)/2;
    if (x <= m)
        modify(k<<1, l, m, x, v);
    else
        modify(k<<1|1, m+1, r, x, v);
    tree[k] = (tree[k<<1] * base[r - m]%mod + tree[k<<1|1]) %mod;
}
long long query(int k, int l, int r, int x, int y) {
    assert(l >= 0 && l <= r);
    if (x <= l && r <= y) {
        return tree[k];
    }
    int m = (l + r)/2;
    if (y <= m)
        return query(k<<1, l, m, x, y);
    else if(x > m)
        return query(k<<1|1, m+1, r, x, y);
    else {
        long long p, q;
        p = query(k<<1, l, m, x, y);
        q = query(k<<1|1, m+1, r, x, y);
        return (p * base[min(y, r) - m]%mod + q) %mod;
    }
}
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    base[0] = 1;
    for (int i = 1; i < MAXN; i++) 
        base[i] = (base[i-1] * 2)%mod;
    char cmd[8], s[8];
    int Q, p, q, n;
    while (scanf("%s", S) == 1) {
        n = strlen(S);
        build(1, 0, n - 1);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d %d", &p, &q);
                if (p == q) {
                    printf("%d\n", n - p);
                    continue;
                } else if (S[p] != S[q]) {
                    puts("0");
                    continue;
                }
                int l = 0, r = min(n - p, n - q) - 1, m, ret = 0;
                long long hp, hq;
                while (l <= r) {
                    m = (l + r)/2;
                    hp = query(1, 0, n-1, p, p + m);
                    hq = query(1, 0, n-1, q, q + m);
                    if (hp == hq)
                        l = m + 1, ret = m;
                    else
                        r = m - 1;
                }
                printf("%d\n", ret + 1);
            } else {
                scanf("%d %s", &p, s);
                S[p] = s[0];
                modify(1, 0, n - 1, p, s[0]);
            }
        }
    }
    return 0;
}