解題區/解題區 - UVa

UVa 12338 - Anti-Rhyme Pairs

contents

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

Problem

給一堆單詞，問任意兩個單詞的最常共同前綴長為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
5
daffodilpacm
daffodiliupc
distancevector
distancefinder
distinctsubsequence
4
1 2
1 5
3 4
4 5
2
acm
icpc
2
1 2
2 2

Output for Sample Input

1
2
3
4
5
6
7
8
Case 1:
8
1
8
4
Case 2:
0
4

Solution

對每一個單詞插入到 Trie 中，詢問任兩個字串的最長共同前綴時，相當於詢問兩個節點之間的最小共同祖先距離根多遠。

解決 LCA 問題，這裡採用離線 tarjan 做法。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
struct Trie {
    int n, label, dist;
    int link[26];
} Node[1048576];
int TrieSize;
int insertTrie(const char* str) {
    static int i, idx;
    for(i = idx = 0; str[i]; i++) {
        if(Node[idx].link[str[i]-'a'] == 0) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[TrieSize].label = TrieSize;
            Node[TrieSize].dist = i + 1;
            Node[idx].link[str[i]-'a'] = TrieSize;
        }
        idx = Node[idx].link[str[i]-'a'];
    }
    Node[idx].n ++;
    return Node[idx].label;
}
vector< pair<int, int> > Q[1048576];// query pair, v - input index.
int visited[1048576], F[1048576];
int LCA[1048576];//input query answer buffer.
int findF(int x) {
    return F[x] == x ? x : (F[x]=findF(F[x]));
}
void tarjan(int u) {// rooted-tree.
    F[u] = u;
    for(int i = 0; i < 26; i++) {//son node.
        int v = Node[u].link[i];
    	if(v == 0)	continue;
        tarjan(v);
        F[findF(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findF(Q[u][i].second);
        }
    }
}
int main() {
    int testcase, cases = 0, x, y, n;
    int mp[131072];
    char s[32767];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        for(int i = 1; i <= n; i++) {
        	scanf("%s", s);
        	int x = insertTrie(s);
        	mp[i] = x;
        }
        scanf("%d", &n);
        
        for(int i = 0; i <= TrieSize; i++)
            visited[i] = 0, Q[i].clear();
        for(int i = 0; i < n; i++) {
        	scanf("%d %d", &x, &y);
        	Q[mp[x]].push_back(make_pair(i, mp[y]));
        	Q[mp[y]].push_back(make_pair(i, mp[x]));
        }
        tarjan(0);
        printf("Case %d:\n", ++cases);
        for(int i = 0; i < n; i++) {
            printf("%d\n", Node[LCA[i]].dist);
        }
    }
    return 0;
}