2020-10-09

#include <set> #include <map> #include <cmath> #include <stack> #include <queue> #include <string> #include <vector> #include<cstring> #include <stdio.h> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn=1e6+5; struct Trie{ int next[30]; }trie[maxn]; int sum[maxn],cnt; void insert(char s[]) { int len=strlen(s),root=0; for(int i=0;i<len;i++){ int c=s[i]-'a'; if(!trie[root].next[c]) trie[root].next[c]=++cnt; sum[trie[root].next[c]]++; root=trie[root].next[c]; } } int find(char s[]) { int len=strlen(s),rt=0; for(int i=0;i<len;i++){ int c=s[i]-'a'; if(!trie[rt].next[c])return 0; rt=trie[rt].next[c]; } return sum[rt]; } int main() { char s[100]; while (gets(s)&&s[0]!='\0'){ insert(s); } while (gets(s)&&s[0]!='\0'){ printf("%d\n",find(s)); } return 0; }