题目链接

算法竞赛进阶指南-56.前缀统计

给定 $N$ 个字符串 $S_1,S_2…S_N$，接下来进行 $M$ 次询问，每次询问给定一个字符串 $T$，求 $S_1 \sim S_N$ 中有多少个字符串是 $T$ 的前缀。

输入字符串的总长度不超过 $10^6$，仅包含小写字母。

输入格式

第一行输入两个整数 $N，M$。

接下来 $N$ 行每行输入一个字符串 $S_i$。

接下来 $M$ 行每行一个字符串 $T$ 用以询问。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1 \le N,M \le 10^5$

输入样例：

3 2
ab
bc
abc
abc
efg

输出样例：

2
0

Method : Trie

Trie模板题

#include <string>
#include <unordered_map>
#include <iostream>

using namespace std;

struct Trie {
private:
    int cnt;
    unordered_map<char, Trie*> son;
public:
    Trie() : cnt(0) {}
    ~Trie() {
        for (auto &s : son) {
            delete(s.second);
        }
    }
    
    void insert(const string& s) {
        Trie* p = this;
        for (char c : s) {
            if (!p->son[c]) {
                p->son[c] = new Trie();
            }
            p = p->son[c];
        }
        p->cnt ++;
    }
    
    int query(const string& s) {
        Trie*p = this;
        for (char c : s) {
            if (!p->son[c]) {
                return 0;
            }
            p = p->son[c];
        }
        return p->cnt;
    }
    
    int start_with(const string& s) {
        int res = 0;
        
        Trie* p = this;
        for (char c : s) {
            if (!p->son[c]){
                break;
            }
            p = p->son[c];
            res += p->cnt;
        }
        
        return res;
    }
};



int main() {
    Trie trie;
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++) {
        string s;
        cin >> s;
        trie.insert(s);
    }
    
    for (int i = 0; i < m; i ++) {
        string s;
        cin >> s;
        printf("%d\n", trie.start_with(s));
    }
        
    return 0;
}

复杂度分析

• 时间复杂度：${O(n* L + m * L)}$， 其中$L$为Trie中字符串的平均长度。

• 空间复杂度：${O(n * L)}$，其中$L$为Trie中字符串的平均长度。