前缀统计

题目

给定N个字符串S1,S2…SN,接下来进行M次询问,每次询问给定一个字符串T,求S1~SN中有多少个字符串是T的前缀。

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

输入格式

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

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

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

输出格式

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

每个答案占一行。

输入样例:

3 2
ab
bc
abc
abc
efg

输出样例:

2
0

分析:

  • trie树模板题
  • 下面给出trie树两种模板解法

代码

  • trie树
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5,English=26;

typedef struct trie{
    int count;
    struct trie *children[English];
}trie;

char s[N];
int n,m;

//创建trie树节点 
trie* creat_trie_node(){ 
    trie *pnode=new trie();
    pnode->count=0;
    for(int i=0;i<English;i++){
        pnode->children[i]=NULL;
    }
    return pnode; 
}

//将key插入trie树 
void trie_insert(trie *root,char *key){
    trie *node=root;
    char *p=key;
    while(*p){
        if(node->children[*p-'a']==NULL){
            node->children[*p-'a']=creat_trie_node();
        }
        node=node->children[*p-'a'];
        p++;
    }
    node->count++; 
}

//前序输出trie树 
void show_trie(trie *root){
    trie *node=root;
    if(node!=NULL){
        for(int i=0;i<English;i++){
            if(node->children[i]) {
                printf("%c ",i+'a');
                show_trie(node->children[i]);
            }
        }
    } 
}

//从trie树种查询结果 
int trie_search(trie *root,char *key){
    trie *node=root;
    char *p=key;
    int ans=0;
    while(*p&&node!=NULL){
        ans+=node->count;
        node=node->children[*p-'a'];
        p++;
    }
    if(node!=NULL) ans+=node->count;
    return ans;
}


int main()
{
    cin>>n>>m;
    trie *root=creat_trie_node();
    for(int i=0;i<n;i++){
        cin>>s;
        trie_insert(root,s);
//        show_trie(root);cout<<endl;
    }
    int ans;
    for(int i=0;i<m;i++){
        cin>>s;
        ans=trie_search(root,s);
        cout<<ans<<endl;
    } 
    return 0;
}
  • 数组模拟trie树
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5,M=5e5+5,W=26;

int trie[M][W],p[M],idx;
char s[N]; 
int n,m;

//k插入trie树数组 
void trie_insert(char *k){ 
    int t=0;
    for(int i=0;k[i];i++){
        int &x=trie[t][k[i]-'a'];
        if(!x) x=++idx;
        t=x;
    }
    p[t]++;
}

//从trie树数组查找k 
int query(char *k){
    int t=0,ans=0;
    for(int i=0;k[i];i++){
        int &x=trie[t][k[i]-'a'];
        if(!x) break;
        t=x;
        ans+=p[t];
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s;
        trie_insert(s);
    }
    for(int i=0;i<m;i++){
        cin>>s;
        cout<<query(s)<<endl;
    }
    return 0;
}

   转载规则


《前缀统计》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录