trie

asdfghjkl123 · 2018-07-06 10:44:18 · 个人记录

给定n个字符串，给定q个询问：该字符串出现次数

n，q<=1000,strlen(s)<=1000

#include<bits/stdc++.h>
using namespace std;
int trie[1000005][26];
int tag[1000005];
int n,q;
char s[1005];
int temp;
void adde()
{
    memset(s,0,sizeof(s));
    cin>>s+1;
    int i=0;
    int lin=0;
    while(s[++i])
    {
        int c=s[i]-'a';
        if(!trie[lin][c])
            trie[lin][c]=++temp;
        lin=trie[lin][c];
    }
    tag[lin]++;
    return;
}
int qr()
{
    memset(s,0,sizeof(s));
    cin>>s+1;
    int i=0,lin=0;
    while(s[++i])
    {
        int c=s[i]-'a';
        if(!trie[lin][c])return 0;
        lin=trie[lin][c];
    }
    return tag[lin];
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)adde();
    for(int i=1;i<=q;i++)printf("%d\n",qr());
    return 0;
}