Trie 树
Trie树又称字典树、单词查找树。是一种能够高效存储和查找字符串集合的数据结构。
插入字符串
对上面已知的tire树，假如插入一个字符串”abdf”，需要进行以下操作：
从字符a开始寻找：
从第一层开始p =0 ,s[p][a]是否存在，若不存在，则创建s[p][a]=++idx; 若存在，不做操作，记p = s[p][a]；
找寻字符b：
查看s[p][b]是否存在，若不存在，创建s[p][b]= ++idx，若不存在，不做操作，p = s[p][a]
同样方法找寻字符’d’，‘f’
查找完成后，把该字符串出现次数加一
void Insert(string str){int p =0;for(int i=0; str[i]!='\0';i++){int u = str[i] - 'a';if(!s[p][u]){s[p][u] = ++idx;}p = s[p][u];}cnt[p] ++;}查找字符串出现次数
从第一个字符开始，如果没找到，直接返回0；一直找到最后一个字符，返回最后一个字符的下一个位置p，返回cnt[p]即为字符串的个数
int find(string str){int p = 0;for(int i =0 ; str[i]!='\0';i++){int u = str[i]-'a';if(!s[p][u]){return 0;}else{p = s[p][u];}}return cnt[p];}完整代码
对应acwing 835题
# include # include using namespace std;const int n = 100010;int s[n][26];int cnt[n];int idx;string str;void Insert(string str){int p =0;for(int i=0; str[i]!='\0';i++){int u = str[i] - 'a';if(!s[p][u]){s[p][u] = ++idx;}p = s[p][u];}cnt[p] ++;}int find(string str){int p = 0;for(int i =0 ; str[i]!='\0';i++){int u = str[i]-'a';if(!s[p][u]){return 0;}else{p = s[p][u];}}return cnt[p];}int main(){int m;int i=0;cin>>m;while(m--){char op;cin>>op>>str;if(op == 'I'){Insert(str);}else{cout<<find(str)<<endl;}}}