不妨设有字符串ab、abc、abd、ba,那么将建立如下的字典树。
这样可以快速查询某个字符串是否出现,出现几次。
#includeusing namespace std; const int N = 100010; int son[N][26], cnt[N], idx; // 26个字母,cnt存编号i下标的个数,下标0为空。 int n; char str[N]; void insert(char str[]) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u] = ++ idx; p = son[p][u]; } cnt[p] ++ ; } int query(char str[]) { int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) return 0; p = son[p][u]; } return cnt[p]; } int main() { scanf("%d", &n); while(n -- ) { char op[2]; // op[1]用于吞掉空格 scanf("%s%s", op, str); if (op[0] == 'I') insert(str); else printf("%dn", query(str)); } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)