Trie字符串统计(字典树查询字符串出现次数)
程序员文章站
2022-04-30 20:38:12
...
思路:字典树
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cstdlib>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
//const int MAX =100;
const double PI = 3.14159265359;
//const int mod = 1e9 + 7;
int n, m;
struct node
{
int x, y;ll num;
bool operator <(const node other)const
{
return num > other.num;
}
};
int trie[400001][26], len, root, tot,sum[400001];
bool p;
void insert(string s)
{
len = s.size();
root = 0;
for (int i = 0; i < len; i++)
{
int id = s[i] - 'a';
if (!trie[root][id]) trie[root][id] = ++tot;
root = trie[root][id];
}
sum[root]++;
}
int search(string s)
{
root = 0;
len = s.size();
for (int i = 0; i < len; i++)
{
int id = s[i] - 'a';
if (!trie[root][id])return 0;
root = trie[root][id];
}
return sum[root];
}
int main()
{
int t;
cin>>t;
while(t--)
{
string x,y;
cin>>x>>y;
if(x[0]=='I')
{
insert(y);
}
else
{
cout<<search(y)<<endl;;
}
}
return 0;
}
上一篇: PHP Curl出现403错误的解决办法_php实例
下一篇: Node.js从入门到放弃(七)
推荐阅读
-
python统计字符串中指定字符出现次数的方法
-
Java统计一个字符串在另外一个字符串出现次数的方法
-
MSSQL sqlserver 统计"一个字符串"在"另一个字符串"中出现的次数的方法
-
PHP实现统计所有字符在字符串中出现次数的方法
-
核心API的使用(给定一个字符串,统计每个字符出现的次数)
-
centos下对文件某些特定字符串分组统计出现次数
-
面试题-给定一段文本,找到包含字段串a,同时剔除包含字符串b的行,然后使用“:”分割取所有列,最后对结果排序,统计每个值出现的次数
-
统计一个字符串中相应字符出现的次数
-
统计一个字符串中相应字符出现的次数
-
使用grep -o统计文件中某个字符串出现的次数