Wannafly挑战赛11 D 题 字符串hash + 卡常
2024-09-07 14:20:00
题目链接
https://ac.nowcoder.com/acm/contest/73#question
map与order_map
https://blog.csdn.net/BillCYJ/article/details/78985895
解析 先把T串的所有状态的hash值存在order_map里面 然后对于每一个模式串计算其每一个长度为len(T)的子串的hash值 若在order_map里面则ans++
这道题1e7的数据查找比较多map(O(log(n)) 查找会比 order_map( O(1) )慢 然后再卡卡常就可以了。。。正解是ex_kmp
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e6+;
const int base=; //base,基数 char s1[maxn],s2[maxn];
ull Hash[maxn],temp[maxn],power=; //记录主串哈希值的数组 int main()
{
scanf("%s",s1+); //从第一位开始输入
int n=strlen(s1+);
Hash[]=;
for(int i=;i<=n;i++)
{
s1[i+n]=s1[i];
power*=base;
Hash[i]=Hash[i-]*base+(ull)s1[i];
}
unordered_map<ull,int> ma;
for(int i=n+;i<=n+n;i++)
{
Hash[i]=Hash[i-]*base+(ull)s1[i];
ma[Hash[i]-Hash[i-n]*power]=;
}
int k;
scanf("%d",&k);
while(k--)
{
int ans=;
scanf("%s",s2+);
int m=strlen(s2+);
if(m<n)
{
printf("0\n");
continue;
}
temp[]=;
for(int i=;i<=m;i++)
{
temp[i]=temp[i-]*base+(ull)s2[i];
if(i>=n&&ma[temp[i]-temp[i-n]*power])
ans++;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- Delphi 获取临时数据集 ClientDataSet
- glib-2.49.4-msys-x86-staticLib.7z
- Spring(八)SSH整合简述
- 简单学C——第六天
- 用java具体代码实现分数(即有理数)四则运算
- Js与flash交互:在html页面中用js与MyReport插件交互
- LeetCode_Spiral Matrix II
- vue中一个dom元素可以绑定多个事件?
- hsdf -- 6.21 -- day6
- c++学习计划
- 2017-2018-2 20165312 实验三《敏捷开发与XP实践》实验报告
- js判断手机系统(Android或IOS),跳转相应下载地址
- __NSArrayI removeObjectAtIndex:]: unrecognized selector sent to instance
- 织梦漏洞可疑PHP文件/article文件夹
- Shell-判断条件总结
- 前端PHP入门-028-文件操作-掌握级别
- Jokewithpermutation (DFS)
- Screen多视窗远程控制管理服务
- java简单发送邮件
- ssh保持连接