AcWing 160. 匹配统计 (哈希+二分) 打卡
2024-09-05 22:53:15
阿轩在纸上写了两个字符串,分别记为A和B。
利用在数据结构与算法课上学到的知识,他很容易地求出了“字符串A从任意位置开始的后缀子串”与“字符串B”匹配的长度。
不过阿轩是一个勤学好问的同学,他向你提出了Q个问题:
在每个问题中,他给定你一个整数x,请你告诉他有多少个位置,满足“字符串A从该位置开始的后缀子串”与B匹配的长度恰好为x。
例如:A=aabcde,B=ab,则A有aabcde、abcde、bcde、cde、de、e这6个后缀子串,它们与B=ab的匹配长度分别是1、2、0、0、0、0。
因此A有4个位置与B的匹配长度恰好为0,有1个位置的匹配长度恰好为1,有1个位置的匹配长度恰好为2。
输入格式
第一行输入三个整数N,M,Q,分别表示A串长度、B串长度、问题个数。
第二行输入字符串A,第三行输入字符串B。
接下来Q行每行输入1个整数x,表示一个问题。
输出格式
输出共Q行,依次表示每个问题的答案。
数据范围
1≤N,M,Q,x≤2000001≤N,M,Q,x≤200000
输入样例:
6 2 5
aabcde
ab
0
1
2
3
4
输出样例:
4
1
1
0
0
题意:要你求原来的字符串的所有起点位置去匹配第二个字符串能匹配多少个字符,然后我们再输入x,看正好匹配长度为x的起点位置有多少个
思路:这个我们看能匹配多少个字符,这里其实匹配也就相当于相等,判断字符串相等自然用哈希,让我们我们又不知道他匹配的长度是多少,我们就需要枚举,既然可以枚举我们就可以优化成二分
求出两个字符串的哈希,然后预处理每个位置,二分长度用map存下来即可
#include<bits/stdc++.h>
#define maxn 200005
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll n,m,q;
char s1[maxn],s2[maxn];
ull dp1[maxn],dp2[maxn],f[maxn];
map<ll,ll> mp;
void hash_code(){
f[]=;
for(int i=;i<=n;i++){
dp1[i]=dp1[i-]*+s1[i]-'a'+;
f[i]=f[i-]*;
}
for(int i=;i<=m;i++){
dp2[i]=dp2[i-]*+s2[i]-'a'+;
}
}
int check(ll dex,ll len){
if(dp1[dex+len-]-dp1[dex-]*f[len]==dp2[len]){
return ;
}
return ;
}
int main(){
cin>>n>>m>>q;
cin>>s1+>>s2+;
hash_code();
for(ll i=;i<=n;i++){
ll l=,r=m+,mn=;
while(l<r){
ll mid=(l+r)/;
if(check(i,mid)){
mn=mid;
l=mid+;
}
else{
r=mid;
}
}
mp[mn]++;
// cout<<mn<<"\n";
}
int x;
for(int i=;i<q;i++){
cin>>x;
cout<<mp[x]<<"\n";
}
} /*
6 2 5
aabcde
ab
0
1
2
3
4
5
*/
最新文章
- ubuntu下修改键位
- 原生js完成拼图小游戏
- VPN各种常见状态码及修复方法
- android开发系列之gradle认识
- Linq to Xml示例
- 如果你喜欢Python 那么你不得不知的几个开源项目
- Oracle数据库之视图与索引
- MapReduce程序依赖的jar包
- Unity 3D 调用摄像头捕获照片 录像
- C语言struct类型
- Xadmin集成富文本编辑器ueditor
- 为什么MOBA、“吃鸡”游戏不推荐用tcp协议——实测数据
- JSP 快速入门
- codeforces24D
- 「Splay」区间翻转
- Deep Learning(花书)教材笔记-Math and Machine Learning Basics(线性代数拾遗)
- Eclipse运行时发生An internal error occurred during:“**************” 的解决办法
- 常用linux命令(项目部署)
- linux(kali,centos)安装vm及其提示缺少c头文件解决方法
- 【12月06日】A股全市场情绪指标整理分析