算法字符串

Trie单串多模式匹配

字数统计: 766字   |   阅读时长: 3分
,

摘要: 单纯多模式匹配

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文看一个 Trie 可以完美解决的字符串匹配需求，单串多模式匹配，且模式中的字符没有限制，也就是单串中的每个字符都有可能是模式串的起始字符，这点与 Trie单串多模式匹配，模式开头为统一特殊字符 中处理过的模式开头为统一特殊字符的情况不同。

由于单串中的每个字符都可能是模式串的起始字符，因此对单串的每个字符都需要在 Trie 中搜索一次。

题目

1065. 字符串的索引对

给出 字符串 text 和 字符串列表 words, 返回所有的索引对 [i, j] 使得在索引对范围内的子字符串 text[i]…text[j]（包括 i 和 j）属于字符串列表 words。

提示:

1
2
3
4
5
6
所有字符串都只包含小写字母。
保证 words 中的字符串无重复。
1 <= text.length <= 100
1 <= words.length <= 20
1 <= words[i].length <= 50
按序返回索引对 [i,j]（即，按照索引对的第一个索引进行排序，当第一个索引对相同时按照第二个索引对排序）。

示例 1:
输入: text = “thestoryofleetcodeandme”, words = [“story”,”fleet”,”leetcode”]
输出: [[3,7],[9,13],[10,17]]

示例 2:
输入: text = “ababa”, words = [“aba”,”ab”]
输出: [[0,1],[0,2],[2,3],[2,4]]
解释:
注意，返回的配对可以有交叉，比如，”aba” 既在 [0,2] 中也在 [2,4] 中

题解

算法： Trie

单串多模式匹配的模板题。将多个模式串插入 Trie。然后枚举单串的每个字符，在 Trie 中查询。注意每个起始字符可能匹配出多个模式串。

代码 (C++)

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
const int ALPHABET = 26;

struct TrieNode
{
    bool terminate;
    vector<TrieNode*> children;
    TrieNode()
    {
        terminate = false;
        children = vector<TrieNode*>(ALPHABET);
    }
};

class Trie
{
public:
    Trie()
    {
        root = new TrieNode();
    }

    ~Trie()
    {
        if(root)
            _delete_sub_tree(root);
    }

    void insert(const string& s)
    {
        TrieNode *iter = root;
        for(const char &ch: s)
        {
            TrieNode *&nxt = (iter -> children)[ch - 'a'];
            if(!nxt)
                nxt = new TrieNode();
            iter = nxt;
        }
        iter -> terminate = true;
    }

    vector<int> search(const string& s, int i)
    {
        // 返回所有的 j: s[i..j] 匹配
        TrieNode *iter = root;
        vector<int> result;
        int j = i;
        int n = s.size();
        while(j < n)
        {
            TrieNode *&nxt = (iter -> children)[s[j] - 'a'];
            if(!nxt)
                return result;
            iter = nxt;
            if(iter -> terminate)
                result.push_back(j);
            ++j;
        }
        return result;
    }

private:
    TrieNode *root;

    void _delete_sub_tree(TrieNode* node)
    {
        for(TrieNode *child: node -> children)
            if(child)
                _delete_sub_tree(child);
        delete node;
        node = nullptr;
    }
};

class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        Trie *trie = new Trie();
        for(const string &s: words)
            trie -> insert(s);
        vector<vector<int>> result;
        int n = text.size();
        for(int i = 0; i < n; ++i)
        {
            vector<int> js = trie -> search(text, i);
            for(int j: js)
                result.push_back({i, j});
        }
        return result;
    }
};
Share