http://hihocoder.com/problemset/problem/1014
#include <stdio.h> #include <stdlib.h> #define MAX 26 typedef struct TNode { int count; struct TNode *head; struct TNode *tail; struct TNode *next; char value; }Node; Node* newNode(char ch) { Node *node = (Node*)malloc(sizeof(Node)); node->count = 0; node->head = NULL; node->tail = NULL; node->next = NULL; node->value = ch; return node; } Node* search(char ch, Node * trie) { while(trie) { if(ch == trie->value) return trie; trie = trie->next; } return NULL; } void buildTrie(char *s, Node *trie) { int n = strlen(s); Node* node = search(s[0], trie->head); if(node == NULL){ node = newNode(s[0]); if(trie->head == NULL) trie->head = trie->tail = node; else {trie->tail->next = node;trie->tail = node;} } node->count++; if(n>1) buildTrie(s+1, node); } int matchCount(char *s , Node * trie) { int n = strlen(s); Node* node = search(s[0], trie->head); if(node == NULL) return 0; if(n>1) return matchCount(s+1,node); return node->count; } int getRoot(Node* trie[], char *s) { int i; for(i=0;i<26;i++) if(trie[i]==NULL) return i; else if(trie[i]->value == s[0]) return i; } void init(Node *trie[]) { int i; for(i=0;i<26;i++) trie[i] = NULL; } int main() { int m,n,i; char s[11]; scanf("%d",&m); Node *trie[26]; init(trie); for(i=0;i<m;i++) { scanf("%s",s); int index = getRoot(trie,s); if(trie[index] == NULL) trie[index] = newNode(s[0]); trie[index]->count++; if(strlen(s)>1) buildTrie(s+1,trie[index]); } scanf("%d",&n); int count; for(i=0;i<n;i++) { count = 0; scanf("%s",s); int index = getRoot(trie,s); if(strlen(s)==1) if(trie[index] != NULL) count = trie[index]->count; if(strlen(s) > 1) count = matchCount(s+1,trie[index]); printf("%d\n",count); } return 0; }