题目描述

样例

算法1

和书上一样，可以使用数组来模拟

trie[N][26]相当于开一个足够大的空间，来容纳可能的字典树节点。
这样有一点不是很好，就是不太直观。算法2的链表法就能比较清晰地和书上的图对应上了。

C++ 代码

#include<bits/stdc++.h>
#define N 1000010
using namespace std;

int trie[N][26], tail[N], tot=0;
int n,m;

void insert(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int ch = s[i]-'a';
        if(trie[p][ch]==0) trie[p][ch] = ++tot;
        p = trie[p][ch];
    }
    tail[p]++;
}

int search(string s){
    int p=0, ans=0;
    for(int i=0;i<s.size();i++){
        p=trie[p][s[i]-'a'];
        if(p==0) return ans;
        ans+=tail[p];
    }
    return ans;
}

int main(){
    cin>>n>>m;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s);
    }
    for(int i=0;i<m;i++){
        cin>>s;
        int res = search(s);
        cout<<res<<endl;
    }
    return 0;
}

对于原文用例：

3 2
ab
bc
abc
abc
efg

在insert过程打印0-tot行的结果

------------------------
tot:2
a b c d e f g h i j k l m n o p q r s t u v w x y z 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
------------------------
tot:2
------------------------
tot:4
a b c d e f g h i j k l m n o p q r s t u v w x y z 
1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
------------------------
tot:4
------------------------
tot:5
a b c d e f g h i j k l m n o p q r s t u v w x y z 
1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
------------------------
tot:5

所以数据较小的时候肯定是存在空间浪费的。

算法2

使用链表

定义字典树的节点类型，有3个变量。
tail表示当前节点是不是某些节点的尾节点。
vector<Node*> next链接到下一个节点。
vector<int> cnt为了体现字符的数量，不同于数组实现，这里需要额外的数组记录。

具体详见代码，相比较算法1，算法2的空间复杂度要低一点。

C++ 代码

#include<bits/stdc++.h>
#define N 1000010
using namespace std;

typedef struct Node{
    int tail=0; //字符串结尾
    vector<Node*> next;
    vector<int> cnt;
    Node(){
        next.assign(26, NULL);
        cnt.assign(26, 0);
    }
};

Node *root = new Node();
int n,m;

void insert(string s){
    Node* p=root;
    for(int i=0;i<s.size();i++){
        int ch = s[i]-'a';
        if(!p->next[ch]) p->next[ch]=new Node();
        p->cnt[ch]++;
        p = p->next[ch];
    }
    p->tail++;
}

int search(string s){
    Node *p = root;
    int ans = 0;
    for(int i=0;i<s.size();i++){
        int ch = s[i]-'a';
        ans += p->tail;
        if(!p->next[ch]) return ans;
        p = p->next[ch];
    }
    ans += p->tail;
    return ans;
}

int main(){
    cin>>n>>m;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        insert(s);
    }
    for(int i=0;i<m;i++){
        cin>>s;
        int res = search(s);
        cout<<res<<endl;
    }
    return 0;
}