【POJ3461】Oulipo（字符串Hash）-白红宇

【POJ3461】Oulipo（字符串Hash）

阅读量：5129 次

发布时间：2019-06-13

本文共 1229 字，大约阅读时间需要 4 分钟。

problem

给定两个字符串s1,s2，求s1在s2中出现了多少次（可重叠）。

len(s1) < 1e4, len(s2) < 1e6。

solution

字符串Hash

介绍：

字符串匹配问题：寻找长为n的主串S中的匹配串T的位置或出现次数。

传统的做法：是枚举所有起始位置，再检查是否匹配。

字符串Hash：比较两个字符串的Hash是否相等。

具体：

如果我们用O(m)的时间计算长为m的字符串Hash值，则总的时间复杂度并没有变化。

所以我们采用滚动哈希的优化技巧。

选择互质常数b,h，设字符串C=c1c2..cm。定义哈希函数H(C) = ((c1*b^m-1)+(c2*b^m-2)+..(cm*b^0))modh

这样就可以递推计算字符串的Hash值。

codes

#include
    
     #include
     
      #include
      
       using namespace std;typedef long long LL;const int maxn = 1e6+10, b = 31;char s1[maxn], s2[maxn];LL power[maxn], HA[maxn];int main(){    //预处理b^n    power[0] = 1;    for(int i = 1; i < maxn; i++)        power[i] = power[i-1]*b;    int T;  cin>>T;    while(T--){        scanf("%s%s",s1+1,s2+1);        int n = strlen(s1+1), m = strlen(s2+1);        //主串的Hash        for(int i = 1; i <= m; i++)            HA[i] = HA[i-1]*b+(LL)(s2[i]-'A'+1);        //匹配串的Hash        LL ha = 0;        for(int i = 1; i <= n; i++)            ha = ha*b+(LL)(s1[i]-'A'+1);        //枚举起点为i，长为n的子串，O(1)计算Hash判断是否匹配        int ans = 0;        for(int i = 0; i <= m-n; i++)            if(ha == HA[i+n]-HA[i]*power[n])ans++;        cout<
       
        <<'\n';    }    return 0;}