前言

开赌！

一、哈希函数

1.用处

哈希函数的作用就是将一个复杂样本转化为一个数字，之后复杂样本的对比就可以转化为数字之间的对比。哈希函数接受一个入参，即复杂样本，输出一个出参，即转化后的数字。举个例子，假如我想对比一下两篇文章是否相同，暴力的方法肯定就是遍历一遍一个字一个字得对比。但这样肯定会很慢，所以可以用一个哈希函数将两篇文章转化成两个数字，在对比时只需要对比两数字是否相等即可。这里，两篇文章就是所谓的复杂样本。

2.特征

（1）入参无限，出参有限

由上述用处可以发现，哈希函数接受的入参的可能性的无限的，但输出的参数是有限的，因为就是一个int或者long long之类的数字而已。

（2）输入同样的样本必得到同样的输出值

哈希函数可以保证在输入一个同样的样本，总会得到相同的数字。也就是说，哈希函数里数字的生成的没有任何随机因素的。

（3）输入不同的样本有可能得到相同的输出值

由第一个特征可以想到，在输入无数个样本时，因为出参是有限的，所以是有可能遇到两个样本具有相同的出参，这就叫作“哈希碰撞”。这个现象理论上无法避免，但通过优化算法可以让发生的概率变得非常小。

（4）输出均匀分布

哈希函数也可以保证在输入大量样本后，不管样本相似度的高低，其所得的数字均匀分布在整个区域内。即使两个样本非常相似，输出的数也有可能千差万别。

二、字符串哈希

1.自然溢出

众所周知，unsigned long long能表示的范围为0~2^64-1。自然溢出就是忽略数字的溢出，可以理解为对2^64取模。

2.原理

定义一个字符串经过哈希函数转化的哈希值为base进制，其中base为质数，过程中让其自然溢出。转化时可以考虑让'a'对应为1，'b'对应为2……，注意不要从0开始。之后就可以用数字的比较代替字符串的比较。

3.子串哈希值的求解

首先，需要构建出pow数组，pow[i]存base的i次方，过程中也让其自然溢出。

其次，需要再构建hash数组，hash[i]的值为上一步的hash值乘以base，再加上当前位置字符转成的数字。其实就和把存有每一位数字的digits数组转成一个a进制int或long long的方法一样，只是每一步的数拿数组记了一下。

经过前面的准备，子串的哈希值就是最右字符的下标的hash值，减去最左字符再往左一个的下标的hash值乘以base的子串长度次方。

举个例子，字符串“abcde”，下标分别为0,1,2,3,4，那么子串“bc”的哈希值为hash[2]，减去hash[0]乘以base的2次方。整体原理可以看作将子串前面的字符串，即hash[0]，通过乘以base的2次方，将其“左移”到和hash[2]代表的子串对齐，然后把前缀减掉。

这样，就可以替代kmp算法了。

同样，字符串哈希也可以替代manacher算法。无非就是来到每个位置，因为是回文，所以可以对右边界r进行二分搜索。如果i到r的子串哈希值和左侧反串的哈希值不同，那就去左侧二分；否则就去右侧二分。所以整体时间复杂度O(n*logn)。

三、题目

1.字符串哈希

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int base=499;

//'0'~'9'：1~10
//'A'~'Z'：11~36
//'a'~'z'：37~62
ll value(char c)
{
    if(c>='0'&&c<='9')
    {
        return c-'0'+1;
    }
    else if(c>='A'&&c<='Z')
    {
        return c-'A'+11;
    }
    else
    {
        return c-'a'+37;
    }
}

ll hashCode(string &s)
{
    ll ans=value(s[0]);
    for(int i=1;i<s.length();i++)
    {
        ans=ans*base+value(s[i]);
    }
    return ans;
}

void solve()
{
    int n;
    cin>>n;
    string s;
    vector<ll>a(n);
    for(int i=0;i<n;i++)
    {
        cin>>s;
        a[i]=hashCode(s);
    }

    //统计种类
    sort(a.begin(),a.end());
    int kind=0;
    for(int i=0;i<n;i++)
    {
        while(i+1<n&&a[i]==a[i+1])
        {
            i++;
        }
        kind++;
    }

    cout<<kind;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个题用set的话会比较麻烦，因为如果存的是一个字符串，那么set在比较是否相同时依然要全过一遍看每个位置是否相同，这样常数时间会非常大。此时就需要用字符串哈希把字符串转成long long类型的数字，然后把数字往set里放就会好很多。

这里定义字符0～9对应1～10，然后依次是大写字符和小写字符。接着就是把每个字符串转哈希值，然后排个序统计种类即可。

这里，value函数读取一个字符，然后输出这个字符对应的数值。hashCode读取一个字符串，然后遍历一遍求出该字符串的哈希值。

2.找出字符串中第一个匹配项的下标

class Solution {
public:

    typedef unsigned long long ll;
    const int base=499;

    int strStr(string haystack, string needle) {
        int n=haystack.length();
        int m=needle.length();

        vector<ll>pow(n);
        vector<ll>hash(n);

        build(pow,hash,n,haystack);

        //待匹配串的哈希值
        ll hash2=needle[0]-'a'+1;
        for(int i=1;i<m;i++)
        {
            hash2=hash2*base+needle[i]-'a'+1;
        }

        for(int l=0,r=m-1;r<n;l++,r++)
        {
            if(subHash(l,r,pow,hash)==hash2)
            {
                return l;
            }
        }
        return -1;
    }

    ll subHash(int l,int r,vector<ll>&pow,vector<ll>&hash)
    {
        ll ans=hash[r];
        if(l>0)
        {
            ans-=hash[l-1]*pow[r-l+1];
        }
        return ans;
    }

    void build(vector<ll>&pow,vector<ll>&hash,int n,string &s)
    {
        pow[0]=1;
        for(int i=1;i<n;i++)
        {
            pow[i]=pow[i-1]*base;
        }
        hash[0]=s[0]-'a'+1;
        for(int i=1;i<n;i++)
        {
            hash[i]=hash[i-1]*base+s[i]-'a'+1;
        }
    }    
};

这个题就能展现字符串哈希在子串匹配问题里的妙用了。

思路就是先build出目标字符串的pow数组和hash数组，然后求出待匹配的字符串的哈希值。之后滑动窗口遍历一遍目标字符串逐个比较即可，有匹配的就直接返回，滑完了都没有就返回-1。

这里，求子串哈希值的subHash函数就是按照公式来即可，注意如果l等于0就不用减直接返回即可。

力扣里好像必须开unsigned long long才行，不然会报错。

3.重复叠加字符串匹配

class Solution {
public:

    typedef unsigned long long ll;
    const int base=499;

    int repeatedStringMatch(string a, string b) {
        int n=a.length();
        int m=b.length();
        
        //a至少要拼到大于m的第一个n的倍数长度
        //如果还不够，那就再拼一次
        //还不行就彻底不行

        //最多的次数
        int k=(m+n-1)/n;//向上取整
        string s;
        for(int cnt=0;cnt<=k;cnt++)
        {
            s+=a;
        }
        int len=s.length();

        vector<ll>pow(len);
        vector<ll>hash(len);

        build(pow,hash,len,s);

        //转哈希值
        ll hash2=b[0]-'a'+1;
        for(int i=1;i<m;i++)
        {
            hash2=hash2*base+b[i]-'a'+1;
        }

        for(int l=0,r=m-1;r<len;l++,r++)
        {
            if(subHash(l,r,pow,hash)==hash2)
            {
                //是否到了第k+1份
                return r<n*k?k:(k+1);
            }
        }
        return -1;
    }

    ll subHash(int l,int r,vector<ll>&pow,vector<ll>&hash)
    {
        ll ans=hash[r];
        if(l>0)
        {
            ans-=hash[l-1]*pow[r-l+1];
        }
        return ans;
    }

    void build(vector<ll>&pow,vector<ll>&hash,int n,string &s)
    {
        pow[0]=1;
        for(int i=1;i<n;i++)
        {
            pow[i]=pow[i-1]*base;
        }
        hash[0]=s[0]-'a'+1;
        for(int i=1;i<n;i++)
        {
            hash[i]=hash[i-1]*base+s[i]-'a'+1;
        }
    } 
};

这个题就需要一点观察了。

观察可得，长度为n的a串要想拼出长度为m的b串，至少得拼到大于m的第一个n的倍数长度。举个例子，假如a串为“abc”，长度为3，b串为“cabcabca”，长度为8。那么a串至少要拼三次拼到9长度才有可能。而如果此时还拼不成，那就再多拼一次，还不行就真不行了。举个例子，假如a串为“abc”，长度为3，b串为“cabcabca”，长度为8。那么正常拼到9长度就是“abcabcabc”，此时可以发现还拼不成，那么就可以再拼一次拼成“abcabcabcabc”，这样就可以拼成了。

所以方法就是先计算出至少拼的次数k，就是n除以m向上取整，然后拼的时候直接拼k+1次。之后就是正常去跑字符串哈希和子串哈希，注意如果匹配的子串不到第k+1份就返回k次，否则就返回k+1次。

4.串联所有单词的子串

class Solution {
public:

    typedef unsigned long long ll;
    const int base=499;

    vector<int> findSubstring(string s, vector<string>& words) {
        int n=s.length();
        int m=words.size();
        int len=words[0].length();

        //按下标模长度的余数分组
        //words中字符串长度为3
        //012 345 678 ……
        //123 456 789 ……
        //234 567 ……
        //-> 滑动窗口

        vector<ll>pow(n);
        vector<ll>hash(n);

        build(pow,hash,n,s);

        //存words中的词频 -> 欠的
        map<ll,ll>mp;
        for(string str:words)
        {
            ll cur=Hash(str);
            mp[cur]++;
        }

        int allLen=len*m;
        vector<int>ans;
        for(int i=0;i<len&&i+allLen<=n;i++)//余数
        {
            map<ll,ll>window;//出现的单词词频
            int debt=m;//欠的个数为数组长度

            //建立窗口
            for(int l=i,r=i+len,part=0;part<m;l+=len,r+=len,part++)
            {
                ll cur=subHash(l,r,pow,hash);
                
                window[cur]++;

                //能凑上
                if(window[cur]<=mp[cur])
                {
                    debt--;
                }
            } 

            //凑齐了
            if(debt==0)
            {
                ans.push_back(i);
            }

            //滑动窗口
            for(int l1=i,r1=i+len,l2=i+allLen,r2=i+allLen+len;r2<=n;
            l1+=len,r1+=len,l2+=len,r2+=len)
            {
                //马上要出窗口的字符串
                ll out=subHash(l1,r1,pow,hash);
                //马上要进窗口的字符串
                ll in=subHash(l2,r2,pow,hash);

                //出窗口，如果是凑的就加回来
                window[out]--;
                if(window[out]<mp[out])
                {
                    debt++;
                }

                //进窗口
                window[in]++;
                if(window[in]<=mp[in])
                {
                    debt--;
                }

                //够了
                if(debt==0)
                {
                    ans.push_back(r1);
                }
            }
        }

        return ans;
    }

    ll subHash(int l,int r,vector<ll>&pow,vector<ll>&hash)
    {
        ll ans=hash[r-1];
        if(l>0)
        {
            ans-=hash[l-1]*pow[r-l];
        }
        return ans;
    }

    void build(vector<ll>&pow,vector<ll>&hash,int n,string &s)
    {
        pow[0]=1;
        for(int i=1;i<n;i++)
        {
            pow[i]=pow[i-1]*base;
        }
        hash[0]=s[0]-'a'+1;
        for(int i=1;i<n;i++)
        {
            hash[i]=hash[i-1]*base+s[i]-'a'+1;
        }
    } 

    ll Hash(string &s)
    {
        int n=s.length();

        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans=ans*base+s[i]-'a'+1;
        }
        return ans;
    }
};

这个题就很有难度了。

首先观察匹配的方式，可以考虑用滑动窗口进行子串匹配，但这样就必须考虑滑动窗口开头的问题。而又因为words里的单词长度都一样，所以可以考虑对目标字符串根据模单词长度的余数进行分组，这样每次滑动窗口移动单词的长度即可。又因为不要求words中的单词的出现顺序，所以可以考虑用“欠债还债”的思想，通过建立欠债表判断窗口中是否都包含了words中的单词。

所以就是先build出目标串的哈希值，然后设置一个map存words中单词的词频，注意这里同样存的是字符串哈希。接着先根据单词长度的余数进行分组，注意这里不能超过words中所有单词的长度总和。之后每次都建立一个window存出现的单词的词频和debt变量记录欠的个数。

然后先是建立窗口，计算出子串哈希值，然后往window里存。如果词频比mp里的小，说明这是一次有效的“还债”，那么就让debt--。之后，先特判一次还没还完，再去滑动窗口。每次先计算出要出窗口的子串哈希和要进窗口的子串哈希，然后分别让其出去和进来。其中记得往window里存或删除，然后根据是否是目标词更新debt，每次都判断一下是否还完了。

5.DNA

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int base=499;
const int MAXN=1e5+5;

vector<ll>powB(MAXN);
vector<ll>hashS(MAXN);
vector<ll>hashP(MAXN);

ll subHash(int l,int r,vector<ll>&hash)
{
    ll ans=hash[r];
    if(l>0)
    {
        ans-=hash[l-1]*powB[r-l+1];
    }
    return ans;
}

void build(int n,string &s,int m,string &p)
{
    powB[0]=1;
    for(int i=1;i<n;i++)
    {
        powB[i]=powB[i-1]*base;
    }
    hashS[0]=s[0]-'a'+1;
    for(int i=1;i<n;i++)
    {
        hashS[i]=hashS[i-1]*base+s[i]-'a'+1;
    }
    hashP[0]=p[0]-'a'+1;
    for(int i=1;i<m;i++)
    {
        hashP[i]=hashP[i-1]*base+p[i]-'a'+1;
    }
} 

//判断是否相同
bool same(int l1,int l2,int len)
{
    return subHash(l1,l1+len-1,hashS)==subHash(l2,l2+len-1,hashP);
}

//二分
//s中的范围
bool check(int l1,int r1)
{
    int diff=0;
    int l2=0;
    
    while(l1<=r1&&diff<=3)
    {
        //二分 -> 长度

        int l=1;//长度为1时！！
        int r=r1-l1+1;
        int m;//s和p在这个区间最长的相等长度
        int len=0;
    
        while(l<=r)
        {
            m=(l+r)/2;
            if(same(l1,l2,m))
            {
                len=m;
                l=m+1;
            }
            else
            {
                r=m-1;
            }
        }

        //找到了一个不同的
        if(l1+len<=r1)
        {
            diff++;
        }

        //来到不一样的位置的下一个位置
        l1+=len+1;
        l2+=len+1;
    }

    //不一样的数量是否大于3
    return diff<=3;
}

void solve()
{
    string s,p;
    cin>>s>>p;
    int n=s.length();
    int m=p.length();

    if(n<m)
    {
        cout<<0<<endl;
        return ;
    }

    //生成s和p的hash数组
    //每次要找区间内的不一样个数 -> 二分
    //每次二分找到第一个不一样的地方，然后计数，去后面接着二分

    build(n,s,m,p);

    int ans=0;
    //枚举开头位置
    for(int i=0;i<=n-m;i++)
    {
        if(check(i,i+m-1))
        {
            ans++;
        }
    }
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();    
    }
    return 0;
}

这个题的思路太离谱了……

因为要求两个字符串的差异不超过3个，所以联想到上面Manacher算法判断不同的思路，那么就可以每次二分去找第一个不同的字符。找到之后让diff++，然后再去后续二分找第二个不同的字符，这样以此类推，如果差异个数diff超过了3个，那就说明不匹配。

具体代码就是上来先build出两个字符串的哈希数组，然后去枚举每个开头位置，去check一下以这个位置开头能否匹配上，能就让ans++，最后返回ans即可。所以check方法就是二分去找不同的个数，只要没超二分的大范围，且差异的个数不超过3个就继续二分。每次考虑二分最长的相等的区间长度，如果两字符串在当前长度内的子串相等，那就记录当前长度，然后去更长的长度二分。当跳出循环时，如果这个长度len在范围内，那就说明找到了一个不同的字符，那就让diff增加，然后让两字符串区间的左边界往后跳去后续二分。

总结

再加把劲！！努力努力再努力！！

END

# 算法 # c++ # leetcode # 哈希算法
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

avatar 魔乐社区
cover

「极限压缩 量化未来」Modelers GeekDay上海站圆满落幕

avatar 魔乐社区
cover

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

avatar 魔乐社区