题目链接

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 ;
}

最新文章

  1. Delphi 获取临时数据集 ClientDataSet
  2. glib-2.49.4-msys-x86-staticLib.7z
  3. Spring(八)SSH整合简述
  4. 简单学C——第六天
  5. 用java具体代码实现分数(即有理数)四则运算
  6. Js与flash交互:在html页面中用js与MyReport插件交互
  7. LeetCode_Spiral Matrix II
  8. vue中一个dom元素可以绑定多个事件?
  9. hsdf -- 6.21 -- day6
  10. c++学习计划
  11. 2017-2018-2 20165312 实验三《敏捷开发与XP实践》实验报告
  12. js判断手机系统(Android或IOS),跳转相应下载地址
  13. __NSArrayI removeObjectAtIndex:]: unrecognized selector sent to instance
  14. 织梦漏洞可疑PHP文件/article文件夹
  15. Shell-判断条件总结
  16. 前端PHP入门-028-文件操作-掌握级别
  17. Jokewithpermutation (DFS)
  18. Screen多视窗远程控制管理服务
  19. java简单发送邮件
  20. ssh保持连接

热门文章

  1. 四、绘图可视化之Seaborn
  2. C05 C语言字符串和数组
  3. 关于POST的请求的问题的汇总
  4. webuploader项目中多图片上传实例
  5. ios之UIActionSheet
  6. 几种常用库在CentOS下的编译
  7. [POJ]1164 The Castle
  8. 【php】 php能做什么
  9. 格式化输出,基本运算符,流程控制主if
  10. [Redis]ResponseError: Client sent AUTH, but no password is set