算法笔记--字符串hash

时间：2023-03-09 02:46:32
算法笔记--字符串hash

概述：

主要用于字符串的匹配。

定义hash函数：

H(c)=(c1bm-1 +c2bm-2 +...+cmb0)mod h

对于字符串c中l-r区间的hash值：

H(l,r)=H(1,r)-H(1,l-1)*br-l+1

如果hash值很大，对h取模，一般地，用unsigned long long 来保存数据，这样溢出时就会自动对264 取模。

如果两个字符串的hash值相等，我们认为它们相同，不排除小概率事件使得两个字符串具有相同的hash值（由取模导致）。

大白书例子：

const ull base=;

//a在b中是否出现

bool contain(string a,string b)

{

    int al=a.length(),bl=b.length();

    if(al>bl)return false;

    //计算base的al次方

    ull t=;

    for(int i=;i<al;i++)t*=base;

    //计算a和b长度为al的前缀对应的hash值

    ull ah=,bh=;

    for(int i=;i<al;i++)ah=ah*base+a[i];

    for(int i=;i<al;i++)bh=bh*base+b[i];

    //对b不断的右移一位，更新hash值并判断

    for(int i=;i+al<=bl;i++)

    {

        if(ah==bh)return true;

        if(i+al<bl)bh=bh*base+b[i+al]-b[i]*t;

    }

    return false;

}

//a的后缀和b的前缀相等的最大长度

int overlap(string a,string b)

{

    int al=a.length(),bl=b.length();

    int ans=;

    ull ah=,bh=,t=;

    for(int i=;i<=min(al,bl);i++)

    {

        ah=ah+a[al-i]*t;

        bh=bh*base+b[i-];

        if(ah==bh)ans=i;

        t*=base;

    }

    return ans;

}

HDU - 4300

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define ull unsigned long long

#define mem(a,b) memset(a,b,sizeof(a))

const ull base=;

int mp[];

int h(string s)

{

    int l=s.size();

    int mn=;

    ull ph=,sh=,t=;

    for(int i=;i<l/;i++)

    {

        ph=ph*base+mp[s[i]-'a'];

        sh=(s[l-i-]-'a')*t+sh;

        if(ph==sh)mn=i+;

        t*=base;

    }

    for(int i=;i<l-mn;i++)putchar(s[i]);

    for(int i=;i<l-mn;i++)putchar(mp[s[i]-'a']+'a');

    puts("");

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int T;

    string s,t;

    cin>>T;

    while(T--)

    {

        cin>>t>>s;

        for(int i=;i<;i++)mp[t[i]-'a']=i;

        h(s);

    }

    return ;

}

相关文章