【字符串哈希】【BKDRhash】【Rabin-Karp算法】模板

#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<set> using namespace std; #define MAXN 100001 typedef unsigned long long ull; const ull seed=31; ull seeds[MAXN]; char s[MAXN],s2[MAXN]; int poss[MAXN]; //暴力字符串比较 bool Strcmp(const char a[],const int &L1,const int &R1, const char b[],const int &L2,const int &R2) { for(int i=L1,j=L2;i<R1;++i,++j) if(a[i]!=b[j]) return 0; return 1; } //自然上溢,L首指针,R尾指针,左闭右开 ull BKDRhash(const char str[],const int &L,const int &R) { ull res=0; for(int i=L;i<R;++i) res=res*seed+str[i]; return res; } //预处理,便于hash(s[i...i+m-1]和hash(s[i+1...i+m]之间的转移) void init_seeds() { seeds[0]=1; for(int i=1;i<MAXN;++i) seeds[i]=seeds[i-1]*seed; } //文本串查找,s文本串,sub子串 int RabinKarp(const char s[],const char sub[]) { int n=strlen(s),m=strlen(sub); ull hsub=BKDRhash(sub,0,m),hs=BKDRhash(s,0,m); for(int i=0;i<=n-m;++i) { if(hs==hsub && Strcmp(s,i,i+m,sub,0,m)) return i; hs=(hs-s[i]*seeds[m-1])*seed+s[i+m];//O(1)转移 } return -1; } int main() { init_seeds(); while(1) { scanf("%s%s",s,s2); printf("%d\n",RabinKarp(s,s2)); } return 0; }