哈希--#103. 子串查找
问文本串在模式串中出现了几次
双哈希，预处理出$b$的$i$次方，哈希转化公式：$sum_i$=($sum_{i-1}$*$b^{len}$+$s_i$+1)%$mod$
1 #include <algorithm> 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #define ull long long 6 using namespace std; 7 const ull b1=131,P1=1000429,maxn=1e6+100,b2=133,P2=19491001; 8 ull power1[maxn],sum1[maxn],power2[maxn],sum2[maxn]; 9 char s1[maxn],s2[maxn]; 10 int main() { 11 power1[0]=1;power2[0]=1; 12 for (int i = 1; i < 1000000; i++) 13 power1[i]=(power1[i-1]*b1)%P1,power2[i]=(power2[i-1]*b2)%P2; 14 scanf ("%s%s",s2+1,s1+1); 15 int n=strlen(s1+1),m=strlen(s2+1); 16 sum1[0]=sum2[0]=0; 17 for (int i = 1; i <= m; i++) 18 sum1[i]=(sum1[i-1]*b1+(ull)(s2[i]+1))%P1,sum2[i]=(sum2[i-1]*b2+(ull)(s2[i]+1))%P2; 19 ull ss1=0,ss2=0; 20 for (int i = 1; i <= n; i++) 21 ss1=(ss1*b1+(ull)(s1[i]+1)) %P1,ss2=(ss2*b2+(ull)(s1[i]+1)) %P2; 22 int ans=0; 23 for (int i = 0; i <= m-n; i++) { 24 if (ss1%P1==((sum1[i+n]-sum1[i]*power1[n])%P1+P1)%P1) 25 if (ss2%P2==((sum2[i+n]-sum2[i]*power2[n])%P2+P2)%P2) ++ans; 26 } 27 printf("%d ",ans); 28 return 0; 29 }