Read a list of words, then some prefixes. For each prefix, print how many of the words start with it. Use a trie that counts, in every node, how many words pass through it, so each prefix takes only as many steps as it has letters.
What to build
A trie in which every node counts the words that pass through it.
Requirements
- Add one to the counter of every node a word enters.
- For a prefix, walk down its letters and print the counter where it ends.
- Print 0 when the path stops early.
Input
A line with n (1 ≤ n ≤ 100), then n words. Then a line with q (1 ≤ q ≤ 100), then q prefixes. Every word and prefix has 1 to 20 lowercase letters. A word may appear more than once; count every copy.
Output
For each prefix, one line with the number of words that start with it. A word starts with itself.
Constraints
1 ≤ n, q ≤ 100, and every word has 1 to 20 lowercase letters.
Example
Input:
5
tea
ten
team
to
inn
3
te
t
x
Output:
3
4
0
Why it works
Every word that starts with a prefix must pass through the node where that prefix ends, so that node's counter is the answer.
Examples
5 tea ten team to inn 3 te t x
3 4 0
2 apple apple 2 apple apples
2 0
Hints
Hint 1
Give each trie node 26 child pointers and a counter of the words that pass through it.
Hint 2
To insert, walk down letter by letter, creating missing nodes with calloc, and add 1 to the counter of every node you enter.
Hint 3
For a prefix, walk down the same way: the answer is the counter of the node where the prefix ends, or 0 if a child is missing.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
struct node {
struct node *child[26];
int pass; /* how many words pass through this node */
};
int main(void) {
struct node *root = calloc(1, sizeof(struct node));
int n, q;
char w[21];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%20s", w);
struct node *cur = root;
for (int j = 0; w[j]; j++) {
int k = w[j] - 'a';
if (!cur->child[k]) cur->child[k] = calloc(1, sizeof(struct node));
cur = cur->child[k];
cur->pass++;
}
}
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%20s", w);
struct node *cur = root;
for (int j = 0; w[j] && cur; j++) cur = cur->child[w[j] - 'a'];
printf("%d\n", cur ? cur->pass : 0);
}
return 0;
}