传送门

分析

居然卡哈希数,万恶的出题人......

感觉我这个方法似乎比较呆,我的代码成功成为了全网最慢的代码qwq

应该是可以直接哈希的

但由于我哈希学的不好又想练练线段树维护哈希,于是就写了个线段树维护了一下哈希值

详见代码

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<unordered_map>
using namespace std;
#define uli unsigned long long
const long long HASH = ;
const long long mod = ;
long long pw[],d[];
long long len[],Ans;
char s[],t1[],t2[];
int is[mod+];
inline void build(long long le,long long ri,long long wh,long long pl,long long k){
len[wh]=ri-le+;
if(le==ri){
d[wh]=k%mod;
return;
}
long long mid=(le+ri)>>;
if(mid>=pl)build(le,mid,wh<<,pl,k);
else build(mid+,ri,wh<<|,pl,k);
d[wh]=(d[wh<<]+d[wh<<|]*pw[len[wh<<]]%mod)%mod;
return;
}
struct node {
long long fi,se;
};
inline node q(long long le,long long ri,long long wh,long long x,long long y){
if(le>=x&&ri<=y)return node{d[wh]%mod,ri-le+};
node Ans,a,b;
long long mid=(le+ri)>>,cnt=;
if(mid>=x)cnt+=,a=q(le,mid,wh<<,x,y);
if(mid<y)cnt+=,b=q(mid+,ri,wh<<|,x,y);
if(cnt==)return a;
if(cnt==)return b;
return node{(a.fi+b.fi*pw[a.se]%mod)%mod,a.se+b.se};
}
int main(){
long long n,m1,m2,i,j,k;
scanf("%s",s);
n=strlen(s);
pw[]=;
for(i=;i<n;i++)pw[i]=pw[i-]*HASH%mod;
long long h1=,h2=;
scanf("%s",t1);
m1=strlen(t1);
for(i=;i<m1;i++)
h1=(h1+(t1[i]-'a')*pw[i]%mod)%mod;
scanf("%s",t2);
m2=strlen(t2);
for(i=;i<m2;i++)
h2=(h2+(t2[i]-'a')*pw[i]%mod)%mod;
for(i=;i<n;i++)
build(,n-,,i,s[i]-'a');
memset(is,-,sizeof(is));
for(i=max(m1,m2);i<=n;i++)
for(j=;j+i-<n;j++){
long long hsh=q(,n-,,j,j+i-).fi;
if(is[hsh]==i)continue;
if(q(,n-,,j,j+m1-).fi==h1&&
q(,n-,,j+i-m2,j+i-).fi==h2)Ans++;
is[hsh]=i;
}
cout<<Ans;
return ;
}

最新文章

  1. 用CIL写程序:你好,沃尔德
  2. NodeJS 模块开发及发布详解
  3. asp.net,cookie,写cookie,取cookie
  4. swift_枚举 | 可为空类型 | 枚举关联值 | 枚举递归 | 树的概念
  5. JS实现关闭当前子窗口,刷新父窗口
  6. zabbix中文乱码解决方法
  7. POJ 1657 Distance on Chessboard 简单的计算问题
  8. ANDROID_MARS学习笔记_S02_013_Gson解析json串
  9. rsync工作机制(翻译)
  10. 使用EF对已存在的数据库进行模块化数据迁移
  11. linux下安装ffmpeg
  12. Maven中央仓库源地址改为阿里云(IDEA)
  13. 【译】如何高效的使用 Git
  14. sql server2008数据库迁移的两种方案
  15. LLDB 3.9.1 安装方法
  16. Linux网络那点事(CentOS、Ubuntu、Kali)
  17. UNIX环境高级编程--第一章 UNIX基础知识
  18. Netty入门(1) - 简介
  19. 11.14java课堂测试
  20. Hyper-v虚拟化

热门文章

  1. uva1315 Crazy tea party(找规律)
  2. python主函数
  3. python 编码 —— codecs 库
  4. zookeeper安装搭建
  5. java-04类和对象课堂练习
  6. notepad++怎么显示项目的目录树?
  7. 【Unity】publishing setting keystore作用
  8. c#多线程实现定时执行代码与lock锁操作
  9. 【转载】BusyBox 简化嵌入式 Linux 系统
  10. spring事务-说说Propagation及其实现原理