统计难题HDUOJ-1251(字典树统计前缀次数)
程序员文章站
2022-06-04 13:03:03
...
思路:字典树模板题
#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;
char s[12];
void insert()
{
len = strlen(s);
root = 0;
for (int i = 0; i < len; i++)
{
int id = s[i] - 'a';
if (!trie[root][id]) trie[root][id] = ++tot;
sum[trie[root][id]]++;
root = trie[root][id];
}
}
int search()
{
root = 0;
len = strlen(s);
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()
{
while (gets(s)&&s[0]!='\0')
insert();
while (~scanf("%s", s))
{
//cout<<s<<endl;
int ans = search();
cout << ans << endl;
}
return 0;
}
上一篇: Linux 下编译安装 ffmpeg