解題區/解題區 - UVa

UVa 12837 - Hasmot Ali Professor

contents

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

Problem

給定一個主字串 S，接著數筆詢問有多少不同的子字串以 X 開頭、Y 結尾。

Sample Input

1
2
3
4
5
6
1
abab
3
a a
a b
ba ab

Sample Output

1
2
3
4
Case 1:
2
2
1

Solution

由於題目是要找不同的子字串，必然會造成比對速度上的問題，由於主子串長度最多 1000，而詢問的 X、Y 長度都小於 10，顯然地窮舉是相當有利。但是詢問次數最多 50000，窮舉起來必須有效率地映射到答案中，因此建議離線把詢問建成一個 Trie，同時避免重複的詢問。

窮舉每個子字串，為了加速匹配，最多跑 O(len * len * 10 * 10)，當決定子字串為 [l, r] 時，遞增起頭指針、遞減結尾指針，對於每一組詢問串成 X#inv(Y)，那麼只需要循序走訪一棵 trie，如此一來速度就提升了不少。

接著考慮如何去重複，關鍵點在於窮舉每個子字串，也依序插入 trie 中，當有新增新的節點時再進行答案的驗證。

也許這類型的題目可以先建造一個 suffix tree，然後想辦法詢問，仔細想想不容易就放棄。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
struct TrieNode {
    int n;
    int link[27];
} Node[1048576<<2];
int TrieSize;
int rename(char c) {
    if ('a' <= c && c <= 'z')
        return c - 'a';
    return 26;
}
void insertTrie(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
}
TrieNode* getTrieNode(const char* str, int root) {
    static int i, idx, c;
    for(i = 0, idx = root; str[i]; i++) {
        c = rename(str[i]);
        if(Node[idx].link[c] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[c] = TrieSize;
        }
        idx = Node[idx].link[c];
    }
    return &Node[idx];
}
const int MAXQL = 10 - 1;
const int MAXQ = 50000;
char ms[MAXQ][32];
int main() {
    int testcase, q, cases = 0;
    char s1[32], s2[32], s[1024];
    int A[1024], B[1024];
    scanf("%d", &testcase);
    while(testcase--) {
    	scanf("%s", s);
        scanf("%d", &q);
        int sn = strlen(s), s1n, s2n, an, bn;
        TrieSize = 2;
        int root1 = 0, root2 = 1;
        memset(&Node[root1], 0, sizeof(Node[root1]));
        memset(&Node[root2], 0, sizeof(Node[root2]));
        for (int i = 0; i < q; i++) {
            scanf("%s %s", s1, s2);
            s1n = strlen(s1), s2n = strlen(s2);
            int m = 0;
            for (int j = 0; j < s1n; j++)
                ms[i][m++] = s1[j];
            ms[i][m++] = '#';
            for (int j = s2n - 1; j >= 0; j--)
                ms[i][m++] = s2[j];
            ms[i][m] = '\0';
            insertTrie(ms[i], root2);
        }
        
        for (int i = 0; i < sn; i++) {
            int idx = root1, idx2, c;
            for (int j = i; j < sn; j++) { // add s[l, r]
                c = rename(s[j]);
                if(Node[idx].link[c] == 0) {
                    TrieSize++;
                    memset(&Node[TrieSize], 0, sizeof(Node[0]));
                    Node[idx].link[c] = TrieSize;
                    // create new node == create distinct substring
                    int idx2 = root2;
                    int L = min(j, i + MAXQL);
                    for (int k = i; k <= L; k++) { // brute head
                        if (Node[idx2].link[rename(s[k])] == 0)	break;
                        idx2 = Node[idx2].link[rename(s[k])];
                        if (Node[idx2].link[rename('#')]) {
                            int idx3 = Node[idx2].link[rename('#')];
                            int R = max(i, j - MAXQL);
                            for (int l = j; l >= R; l--) { // brute tail
                                if (Node[idx3].link[rename(s[l])] == 0)	break;
                                idx3 = Node[idx3].link[rename(s[l])];
                                Node[idx3].n ++; // [l, r] = strA + ... + strB
                            }
                        }
                    }
                }
                idx = Node[idx].link[c];
            }
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < q; i++) {
            TrieNode *p = getTrieNode(ms[i], root2);
            printf("%d\n", p->n);
        }
    }
    return 0;
}
/*
1
abab
3
a a
a b
ba ab
*/