The title is direct.
Subject matter
I’ll give you a $n$string. Save it in a dictionary. Here’s another $m for each query, one string for each query, and in the dictionary, find out how many strings are prefixed with this string.
The idea of solving the problem
Template problem
Setting a variable of $sig $at each point indicates the number of words prefixed with strings of characters passing through the path.
$Trie$ Tree. In $insert$operation, add $sig$to the point passed through the path $1$.
$sig$is directly output when querying.
Attach the code
#include <iostream> #include <cstring> #include <cstdio> using namespace std; int n, m; char s[15]; struct node { int sig; node *nxt[30]; }*root; inline node * build() { node *k = new(node); k->sig = 0; memset(k->nxt, NULL, sizeof(k->nxt)); return k; } inline void insert(char *s) { char *word = s; node *rt = root; int id; while(*word) { id = *word - 'a'; if(rt->nxt[id] == NULL) rt->nxt[id] = build(); rt = rt->nxt[id]; rt->sig ++; word ++; } } inline int query(char *s) { node *rt = root; char *word = s; int id; while (*word) { id = *word - 'a'; if(rt->nxt[id] == NULL) return 0; rt = rt->nxt[id]; word ++; } return rt->sig; } int main() { scanf("%d", &n); root = build(); for(int i=1; i<=n; i++) { scanf("%s", s); insert(s); } scanf("%d", &m); for(int i=1; i<=m; i++) { scanf("%s", s); printf("%d\n", query(s)); } return 0; }