AcWing 835. Trie字符串统计--慢慢来,比较快
原题链接
简单
作者:
bruce
,
2020-12-05 22:45:07
,
所有人可见
,
阅读 593
/**
* trie 高效存储+查询字符串,所谓高效就是在存储相同字符串的前缀的时候,使用p指针来自动跳过已经存过
* 的数组,这样极大地简化了存储的空间;
* 举个例子是王道:
* 比如第一次存储的是abab;
* 然后遍历这个字符串,
* int p = 0;// 初始化p,idx = 0;
* i = 0; u = 0;
* son[0][0] = ++idx = 1
* p = son[0][0] = 1;
* -------------------
* i = 1; u = 1;
* son[1][1] = ++idx = 2;
* p = son[1][1] = 2
* -------------------
* i = 2; u = 2
* son[2][0] = ++idx = 3;
* p = son[2][0] = 2;
* i = 3; u = 3;
* son[3][1] = ++idx = 4;
* p = son[3][1] = 4
* cnt[p] = cnt[4] = 1;
// 第一次插入结束,cnt[p],idx都已更新
* 第二次插入,比如插入ab,这里ab是重复的前缀,可以体现出存储的优越性:
* int p = 0;idx = 4; // p 已经初始化
* i = 0; u = 0;
* if(!son[0][0]) 之前存在,所以直接 p = son[0][0] = 1;
* -----------------------
* i = 1; u = 1, p = 1;
* if(!son[1][1]) 存在了,所以 p = son[1][1] = 2
* 最后执行cnt[p]++ = cnt[2]= 1;
* 所以通过上述例子,插入相同前缀的话,可以很大节省和高效存储;
*/
#include<iostream>
#include<string>
using namespace std;
const int N = 100010;
int cnt[N], son[N][26], idx;
void insert(string str)
{
int p = 0;
for(int i=0;i<str.size();i++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
cnt[p]++;
}
int query(string str)
{
int p = 0;
for(int i=0;i<str.size();i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin>>n;
while(n--)
{
string op, str;
cin>>op>>str;
if(op=="I") insert(str);
else printf("%d\n", query(str));
}
}
最后一行错了吧, 应该是 p = 3;