博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
(模板)字符串哈希
阅读量:6572 次
发布时间:2019-06-24

本文共 1098 字,大约阅读时间需要 3 分钟。

#include 
#include
#include
#include
#include
using namespace std;#define res register int/*#define getchar gctypedef long long LL;char buf[1<<23],*fc=buf,*tc=buf;inline char gc(){ if(fc==tc) { tc=(fc=buf)+fread(buf,1,1<<23,stdin); if(fc==tc) return EOF; } return *fc++;}*/inline int read(){ int x=0,f=1;char ch; while(!isdigit(ch=getchar())) if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return f*x;}const int N=1000000+10;char s[N];int len,q;unsigned long long f[N],p[N];const unsigned long long P=131;inline unsigned long long calc(int l,int r){ return f[r]-f[l-1]*p[r-l+1];}int main(){ scanf("%s",s+1); len=strlen(s+1); scanf("%d",&q); p[0]=1; for(res i=1 ; i<=len ; ++i) { f[i]=f[i-1] * P + (s[i]-'a'+1);//hash of 1~i p[i]=p[i-1] * P;//P^i } for(res i=1 ; i<=q ; ++i) { int l1,r1,l2,r2; scanf("%d %d %d %d",&l1,&r1,&l2,&r2); if(calc(l1,r1)==calc(l2,r2)) puts("Yes"); else puts("No"); } return 0;}

  

转载于:https://www.cnblogs.com/wmq12138/p/10779294.html

你可能感兴趣的文章
html标签的显示模式(块级标签,行内标签,行内块标签)(转)
查看>>
maven项目无法查看方法
查看>>
7个你可能不认识的CSS单位:rem vh vw vmin vmax ex ch
查看>>
stark组件(1):动态生成URL
查看>>
汕头市队赛 SRM 09 B 撕书
查看>>
javascript常用的内置对象实用操作
查看>>
KVC+Runtime获取类/对象的属性/成员变量/方法/协议并实现字典转模型
查看>>
169. Majority Element
查看>>
Django Form表单学习总结
查看>>
大整数加法
查看>>
Vue 爬坑之路(四)—— 与 Vuex 的第一次接触
查看>>
深入理解OOP(三):多态和继承(动态绑定和运行时多态)
查看>>
下拉菜单
查看>>
C/C++中extern关键字详解
查看>>
证书吊销
查看>>
让height: 100%生效
查看>>
Linux文件查找命令find,xargs详述【转】
查看>>
python实战===教你用微信每天给女朋友说晚安【转】
查看>>
SQL 数据库知识点回顾
查看>>
[清华集训2014]玛里苟斯
查看>>