首页 > 其他分享 >P10470 前缀统计(trie树)

P10470 前缀统计(trie树)

时间:2024-09-14 10:23:55浏览次数:10  
标签:typedef return 前缀 P10470 trie long int vector vx

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int idx;
int ne[N][26],isend[N];
void insert(string &s)
{
	int p = 0;
	int n = s.size();
	for(int i=0;i<n;++i)
	{
		int x = s[i]-'a';
		if(!ne[p][x]) ne[p][x] = ++idx, p = idx;
		else p = ne[p][x];
	}
	isend[p]++;
}
int query(string &s)
{
	int p = 0;
	int n = s.size();
	int sum = 0;
	for(int i=0;i<n;++i)
	{
		int x = s[i]-'a';
		if(!ne[p][x]) return sum;
		else p = ne[p][x], sum+=isend[p];
	}
	return sum;
}
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;++i)
	{
		string s;
		cin>>s;
		insert(s);
	}
	for(int i=0;i<m;++i)
	{
		string s;
		cin>>s;
		cout<<query(s)<<'\n';
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:typedef,return,前缀,P10470,trie,long,int,vector,vx
From: https://www.cnblogs.com/ruoye123456/p/18413456

相关文章

  • 【每日一题】LeetCode 2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和
    【每日一题】LeetCode2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和、堆(优先队列))题目描述给定两个整数数组chargeTimes和runningCosts,分别代表n个机器人的充电时间和运行成本。再给定一个整数budget,表示预算。我们需要计算在不超过预算的情况下,最......
  • nvm下载node版本Could not retrieve https://nodejs.org/dist/latest/SHASUMS256.txt.
    1.使用nvm安装node版本的时候报错Couldnotretrievehttps://nodejs.org/dist/latest/SHASUMS256.txt.Get"https://nodejs.org/dist/latest/SHASUMS256.txt":dialtcp104.20.22.46:443:i/otimeout原因:可能是远程连接被关闭的问题,这是由于国内网络限制导致的,解决办法:找到sett......
  • [模板题] - 208. 实现 Trie (前缀树)
    题目链接208.实现Trie(前缀树)思路模板题-Trie树题解链接官方题解关键点无时间复杂度\(O(\sum_{i}\#\text{word}_{i})\)空间复杂度\(O(\sum_{i}\#\text{word}_{i})\)代码实现:classTrie:def__init__(self):self.children=[N......
  • DBeaver 连接 mysql 报错:Public Key Retrieval is not allowed
    前言DBeaver连接mysql报错:PublicKeyRetrievalisnotallowed遇到"PublicKeyRetrievalisnotallowed"错误时,通常意味着你正在使用的身份验证方法需要加密连接,但是没有正确地配置客户端或服务器来支持这种加密。解决第一种可以在连接字符串中添加allowPublicKeyRe......
  • tailwindcss学习:2 自定义类的使用和常见的tailwindcss前缀
    1.自定义类的定义在Tailwind CSS中,您可以通过 tailwind.config.js 文件定义自定义类。类似 border-custom-green 这种写法实际上是一个组合类,通常是由自定义类和内置类结合而成的。示例:自定义边框颜色假设您在 tailwind.config.js 中定义了一个自定义颜色://tailwi......
  • 浅谈高维前缀和
    之前做了一道高维前缀和题做着做着忘掉怎么写了,遂记一发。你说的对,但是我谈的真的很浅。铺垫回忆一下我们求前缀和是怎么求的。一维前缀和:for(inti=1;i<=n;i++){ s[i]=s[i-1]+a[i];}没有任何问题对吧。而求二维前缀和时,我们通常会使用如下方法求前缀和(如果不是当我没说......
  • 信息学奥赛初赛天天练-87-NOIP2014普及组-完善程序-矩阵、子矩阵、最大子矩阵和、前缀
    1完善程序最大子矩阵和给出m行n列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。输入第一行包含两个整数m和n,即矩阵的行数和列数。之后m行,每行n个整数,描述整个矩阵。程序最终输出最大的子矩阵和。(最后一空4分,其余3分,共16分)比如在如下这个矩阵中:440-2-7......
  • 洛谷 B3645 数列前缀和 2 题解
    前缀知识:枚举,费马小定理,逆元,线性乘法逆元,线段树(?)。解法1:暴力如题。暴力枚举即可,30分。由于太简单,不给代码。解法2:前缀积+费马小定理+逆元由于涉及静态区间,可以想到前缀积。前缀积公式为\(q_r/q_{l-1}\),除法恰好可以用逆元来算。直接写即可。不会超时,因为时间为\(O(n\logp)\)......
  • 14.最长公共前缀
    14.最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串“”。示例1:输入:strs=[“flower”,“flow”,“flight”]输出:“fl”示例2:输入:strs=[“dog”,“racecar”,“car”]输出:“”解释:输入不存在公共前缀。提示:1<......
  • 高维前缀和 (SOSDP)
    算法介绍——高维前缀和引入我们都知道二维前缀和有这么一个容斥的写法:for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}}那换成三维前缀和,就有如下容斥代码:\[s[i][j][k]=a[i][j][k]+s[i-1][j][k]+s[......