洛谷P2292《[HNOI2004]L语言》

三月 09, 2019 3864

Trie 的经典应用

题目描述

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。

例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的，因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解，而且是在字典D下能够被理解的最长的前缀。

给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。

输入输出格式

输入格式

输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。之后的n行每行描述一个单词，再之后的m行每行描述一段文章。

其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。

输出格式

对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。

输入输出样例

输入样例#1

1
2
3
4
5
6
7
8
4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

输出样例#1

1
2
3
14  （整段文章’whatisyourname’都能被理解）
6  （前缀’whatis’能够被理解）
0  （没有任何前缀能够被理解）

解题思路

这里选用 Trie 来做

首先把所有的单词扔进树里，记一下最长单词的长度

枚举字符串的右端点 r \in [0, \text{The string's length} - 1]
字符串的左端点 l \in [max(r - \text{Max Length}, -1), r]

判断一下这个子串 s[l + 1, r] 在 Trie 里是不是一个完整的单词，是的话就把答案更新为 r + 1 并退出枚举左端点的循环

判断单词是否完整只要对每个单词的结尾字母打个标记就行

代码实现

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
#include <iostream>
#include <cstring>
#include <string>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)
#define TREE_ROOT 0

using std::cin;
using std::cout;
using std::endl;

const int MAXCHAR = 1024 * 1024 + 10;

int maxlength;

struct Trie{
    // 日常封装
    struct Node {
        int size;
        int linkson[26 + 1];
        // 直接用它来记子节点的位置，类似于链表
        
        bool last;
        
        Node() {
            size = 0;
            last = false;
            memset(linkson, 0, sizeof linkson);
        }
    } tree[MAXCHAR];
    
    int cnt;
    
    Trie() { cnt = 0; }
    
    void Insert(const char *s, int length) {
        // 插入
        int pos = 0; // pos = root
        maxlength = std::max(maxlength, length);
        for (int i = 0; i < length; ++i) {
            int ins = s[i] - 'a';
            if (tree[pos].linkson[ins] == 0) {
                // insert
                tree[pos].linkson[ins] = ++cnt;
                ++tree[pos].size;
            }
            pos = tree[pos].linkson[ins];
        }
        tree[pos].last = true;
    }
    short Find(const char *s, int l, int r) {
        int pos = 0; // pos = root
        for (int i = l; i <= r; ++i) {
            int que = s[i] - 'a';
            if (tree[pos].linkson[que] == 0) return 0;
            pos = tree[pos].linkson[que];
            // 这里也是和上边插入一模一样
        }
        return tree[pos].last;
    }
} T;

int n, m;
bool dp[MAXCHAR];

int main() {
    IMPROVE_IO();
    cin >> n >> m;
    std::string s;
    for (int i = 1; i <= n; ++i) {
        cin >> s;
        T.Insert(s.c_str(), (int) s.size());
    }
    for (int i = 1; i <= m; ++i) {
        cin >> s;
        memset(dp, 0, sizeof dp);
        int ans = 0;
        int len = (int) s.size();
        for (int r = 0; r < len; ++r) {
            // 枚举右端点
            for (int l = std::max(r - maxlength, -1); l <= r; ++l) {
                // 枚举左端点
                if ((l == -1 || dp[l]) && T.Find(s.c_str(), l + 1, r)) {
                    dp[r] = true;
                    ans = r + 1;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}