1 条题解

  • 0
    @ 2025-10-8 16:52:53
    #include<bits/stdc++.h>
    using namespace std;
    typedef unsigned long long ULL;
    const int N=1110000;
    char s1[N],s2[N];
    ULL f[N],d[N];
    ULL Hash(int l,int r)
    {
    	return f[r]-f[l-1]*d[r-l+1];
    }
    int main()
    {
        scanf("%s%s",s1+1,s2+1);
        int len1=strlen(s1+1),len2=strlen(s2+1);
        d[0]=1;
        for(int i=1;i<=len1;i++)
        {
            f[i]=f[i-1]*131+s1[i];//让其对(2^64 -1 )自动溢出,相当于 %(2^64 -1 )
            d[i]=d[i-1]*131;
        }
        ULL t=0;for(int i=1;i<=len2;i++) t=t*131+s2[i];
        int ans=0;
        for(int i=1;i<=len1-len2+1;i++)
            if(Hash(i,i+len2-1)==t)ans++;
        printf("%d\n",ans);
        return 0;
    }
    
    • 1

    *【字符串:hash值】统计字符串出现的次数[Oulipo]

    信息

    ID
    3154
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    168
    已通过
    38
    上传者