字符串Hash

Hash的核心思想在于,将输入映射到一个值域较小、可以方便比较的范围。

字符串hash通常用来比较字符串是否相等,在O(1)的时间复杂度内

对于字母x

设idx(x)=x-'a'+1

单Hash公式:

hasd[i]=(hash[i-1]*p+idx(i) )%mod

举例:

假设p=13,mod=101,对字符串abc进行Hash演算
hash[0] = 1
hash[1] = (hash[0] * 13 + 2) % 101 = 15
hash[2] = (hash[1] * 13 + 3) % 101 = 97

则字符串abc的hash值为97

双Hash方法:

将一个字符串用不同的mod hash两次,将这两个结果用一个二元组表示,表示作为Hash的结果。

hash1[i]=(hash1[i-1]*p+idx(s[i]))%mod1

hash2[i]=(hash2[i-1]*p+idx(s[i]))%mod2

hash结果为<hash1[n],hash2[n]>

双hash比较安全稳定,当然可以用三hash,更稳

base={73,87,61}

mod={100000007,998244353,100000009}

计算子串的Hash:

推导不想写了,感兴趣的可以去原博客看一看,在这里直接给出公式

hash=((hash[r]hash[l1]p^(rl+1))%mod+mod)%mod

这是计算以l为首,r为尾的子串hash

以下是hash可供选择的一些素数:

53、97、193、389、769、1543、3079、6151、12289、24593、49157、98317、196613、393241、786433、1572869、3145739、6291469、6291469、1258917、25165843、 50331653、100663319、201326611、402653189、805306457、1610621741

参考文章:https://blog.csdn.net/pengwill97/article/details/80879387

例题:

原题链接:https://nanti.jisuanke.com/t/44597

来自前天周赛的一道题目,就是给你一个只含数字的串,划分为若干个块,若干个块合起来为回文串,问最大划分为多少

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll has[2000005];
ll p=13,mod=1610612741;
ll apow(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1)
        {s=s*a%mod;}
        a=a*a%mod;
        b>>=1;
    }
    return s;
}
int main()
{
    char s[2000005];
    gets(s);
    ll n=strlen(s);
    for(int i=0;i<n;i++)
    {
        int j=i+1;
        has[j]=((has[j-1]*p)+(s[i]-'0'+1))%mod;
    }
    ll ans=0;
    int start=1,last=n;
    while(start<=last)
    {
        for(int j=1;j<=n;j++)
        {
            ll a1=((has[start+j-1]-has[start-1]*apow(p,j))%mod+mod)%mod;
            ll a2=((has[last]-has[last-j]*apow(p,j))%mod+mod)%mod;
            if(a1==a2)
            {
                if(start+j-1==last)
                {
                    ans++;
                    start+=j;
                    last-=j;
                    break;
                }
                ans+=2;
                start+=j;
                last-=j;
                break;
            }
        }
        if(start>last)
        {break;}
    }
    printf("%lld\n",ans);
    return 0;
}

codeforces-E. Compress Words

原题链接:https://codeforces.ml/contest/1200/problem/E

题意大体是给你若干个单词,相互之前进行拼接,若有重复的则删掉一种,比如sample please拼接后变成samplease

这道正解应该是KMP,但是hash也能做

于是写完交上去WA3,WA了11次。。。

这道题卡单hash好像。。。

于是改用三hash,稳

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mod[4]={0,1000000007,998244353,1000000009};
ll p[4]={0,73,87,61};
ll h[4][1000006],d[4][1000006];
ll apow(ll a,ll b,ll k)
{
    ll s=1;
    while(b)
    {
        if(b&1)
        {s=s*a%mod[k];}
        a=a*a%mod[k];
        b>>=1;
    }
    return s;
}
string s[100005];
int main()
{
    ll n;
    cin>>n;
    for(int i=0;i<n;i++)
    {cin>>s[i];}
    int lon=s[0].size();
    for(int j=0;j<lon;j++)
    {
        if(j==0)
        {h[1][0]=(s[0][j]-'0'+1)%mod[1];
        h[2][0]=(s[0][j]-'0'+1)%mod[2];
        h[3][0]=(s[0][j]-'0'+1)%mod[3];}
        else
        {h[1][j]=(h[1][j-1]*p[1]+s[0][j]-'0'+1)%mod[1];
        h[2][j]=(h[2][j-1]*p[2]+s[0][j]-'0'+1)%mod[2];
        h[3][j]=(h[3][j-1]*p[3]+s[0][j]-'0'+1)%mod[3];}
    }
    cout<<s[0];
    for(int i=1;i<n;i++)
    {
        int len=s[i].size(),val=0;
        ll a1,a2,a3,b1,b2,b3;
        for(int j=1;j<=len;j++)
        {
            if(j>lon)
            {break;}
            if(j==lon)
            {a1=h[1][lon-1];
            a2=h[2][lon-1];
            a3=h[3][lon-1];}
            else
            {a1=((h[1][lon-1]-h[1][lon-1-j]*apow(p[1],j,1))%mod[1]+mod[1])%mod[1];
            a2=((h[2][lon-1]-h[2][lon-1-j]*apow(p[2],j,2))%mod[2]+mod[2])%mod[2];
            a3=((h[3][lon-1]-h[3][lon-1-j]*apow(p[3],j,3))%mod[3]+mod[3])%mod[3];}
            if(j==1)
            {d[1][0]=(s[i][j-1]-'0'+1)%mod[1];
            d[2][0]=(s[i][j-1]-'0'+1)%mod[2];
            d[3][0]=(s[i][j-1]-'0'+1)%mod[3];}
            else
            {d[1][j-1]=(d[1][j-2]*p[1]+s[i][j-1]-'0'+1)%mod[1];
            d[2][j-1]=(d[2][j-2]*p[2]+s[i][j-1]-'0'+1)%mod[2];
            d[3][j-1]=(d[3][j-2]*p[3]+s[i][j-1]-'0'+1)%mod[3];}
            b1=d[1][j-1];b2=d[2][j-1];b3=d[3][j-1];
            if(a1==b1&&a2==b2&&a3==b3)
            {val=j;}
        }
        for(int j=val;j<len;j++)
        {
            h[1][lon]=(h[1][lon-1]*p[1]+s[i][j]-'0'+1)%mod[1];
            h[2][lon]=(h[2][lon-1]*p[2]+s[i][j]-'0'+1)%mod[2];
            h[3][lon]=(h[3][lon-1]*p[3]+s[i][j]-'0'+1)%mod[3];
            cout<<s[i][j];lon++;
        }
    }
    cout<<endl;
    return 0;
}

123

点赞
  1. suddenly说道:
    Google Chrome Windows 7

     ̄﹃ ̄

发表评论

电子邮件地址不会被公开。必填项已用 * 标注