Algoogle

Algorithm for Programming Contest

PKU 3193 Cow Phrasebook

Category: PKU Tag: data-structure, string

Cow Phrasebook

問題概要


辞書と牛の言葉が与えられる.
牛の言葉の中で, 辞書にある文字列の0文字目から牛の言葉の長さ分まで一致するものがある数はいくらか

解法


トライ木を作ればいい.
abc
ade
bcfg
みたいな文字列があるとき, 図のような木をつくる.
pku3193-01
rootから木を辿ってもし文字列の途中で辿れなくなったら一致するものはない.

コード


(3193.cpp) download
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
#include <algorithm>
#include <cstring>
#include <iostream>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int N, M;
vector<string> pattern;

struct PMA{
    PMA* next[256];
    PMA(){ memset(next,0,sizeof(next));}
    ~PMA(){ for(int i = 0; i < 256; i++)if(next[i]) delete next[i];}
};

PMA *buildPMA(){
    PMA *root = new PMA, *now;
    root->next[0] = root;
    for(int i = 0; i < pattern.size(); i++){
        now = root;
        for(int j = 0; j < pattern[i].size(); j++){
            if(!now->next[pattern[i][j]])
                now->next[pattern[i][j]] = new PMA;
            now = now->next[pattern[i][j]];
        }
    }
    return root;
}

int match(PMA *root, const string a){
    PMA *pma = root;
    for(int i = 0; i < a.size(); i++){
        int c = a[i];
        if(!pma->next[c]) return 0;
        pma = pma->next[c];
    }
    return 1;
}

int main(){
    cin.sync_with_stdio(0);
    cin >> M >> N;
    cin.ignore();
    for(int i = 0; i < M; i++){
        string a; getline(cin, a);
        pattern.push_back(a);
    }
    PMA *pma = buildPMA();
    int ans = 0;
    for(int i = 0; i < N; i++){
        string a; getline(cin, a);
        ans += match(pma, a);
    }
    cout << ans << endl;
    return 0;
}

Comments