題意：
? ? ?給你一些模式串，然后給你一些提問，每個提問是給你一個串，問你這個串在上
面的模式串中出現的次數。

思路：

? ? ? 一開始想到hash,但是因為用的是map，所以超時了，map的操作是有代價的，他本身還會排序的，所以超時了，想用vec結果還沒弄出來這個類型hash["aaa"] = 1,最后只能字典樹了，先想下字典樹，字典樹處理前綴的出現的次數的時候非常拿手的，對于這個題目，我們可以把每個串都拆開，拆成一個一個的，然后在把他們加在樹里面，這樣就OK了，還有一個關鍵的地方，就是比如拆這個串 aa 可以拆成 a ,a ,aa，所以我們要在第一個a的時候只累加一次，怎么做到呢，可以在Tree的結構體里面在開個變量，標記當前這個字母最后一次是被誰更新的，如果是自己，那么就不會V++.

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Tree {Tree *next[26];int v ,mk; }Tree;Tree root;void Buid_Tree(char *str ,int mkk) {int len = strlen(str);Tree *p = &root ,*q;for(int i = 0 ;i < len ;i ++){int id = str[i] - 'a';if(p -> next[id] == NULL){q = (Tree *) malloc(sizeof(root));q -> v = 1;q -> mk = mkk;for(int j = 0 ;j < 26 ;j ++)q -> next[j] = NULL;p -> next[id] = q;p = p -> next[id];}else{p = p -> next[id];if(p -> mk != mkk) p -> v ++;p -> mk = mkk;}} }int Find(char *str) {int len = strlen(str);Tree *p = &root;for(int i = 0 ;i < len ;i ++){int id = str[i] - 'a';p = p -> next[id];if(p == NULL) return 0;}return p -> v; }int main () {char str[25];int n ,m ,i;while(~scanf("%d" ,&n)){for(i = 0 ;i < 26 ;i ++)root.next[i] = NULL;for(i = 1 ;i <= n ;i ++){scanf("%s" ,str);int len = strlen(str) - 1;for(int ii = 0 ;ii <= len ;ii ++){char now[25];for(int jj = 0 ;jj + ii <= len ;jj ++){now[jj] = str[ii + jj];now[jj+1] = '\0';Buid_Tree(now ,i);}}}scanf("%d" ,&m);for(i = 1 ;i <= m ;i ++){scanf("%s" ,str);printf("%d\n" ,Find(str));}}return 0; }

總結

以上是生活随笔為你收集整理的hdu2846 字典树(带id的)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。