字元串Hash學習筆記

• 2022 年 3 月 12 日
• 筆記
• 學習筆記

目錄

• 第一節 ：什麼是字元串Hash
• 第二節 ：字元串Hash的求解過程
• 第三節 ：真題實例與分析

第一節

什麼是字元串Hash？ (RK演算法)

• 如果兩個字元串hash後的值不相同，則它們肯定不相同。
• 如果它們hash後的值相同，它們不一定相同。
• RK演算法的基本思想就是：將模式串 \(P\) 的hash值跟主串 \(S\) 中的每一個長度為 \(|P|\) 的子串的hash值比較。如果不同，則它們肯定不相等；如果相同，則再逐位比較之。

第二節

字元串Hash的求解過程

• 設模式串為 \(P\) ，其長度為 \(m\) ，主串為 \(S\) ，其長度為 \(n\) 。
• 則模式串 \(P\) 可以看作是一個 \(m\) 位的 \(d\) 進位數 \(A\) ，主串 \(S\) 可以看作是一個 \(n\) 位的 \(d\) 進位數。我們的模式匹配過程就是將 \(A\) 與主串中的每個長度為 \(m\) 的 \(d\) 進位數 \(S[t…t+m-1]\) （ \(t\) = \(0\) , \(1\) , \(2\) ,…,\(n-m+1\) ）的值做比較，所以整個模式匹配過程就變成了兩個 \(d\) 進位數之間的比較過程。
• 例如模式串為 \(123\) ，主串為 \(65127451234\) ，就是將十進位數 \(123\) 跟十進位數 \(651\) , \(512\) , \(127\) , \(274\) , \(745\), \(451\) , \(512\) , \(123\) 的逐個比較過程。

第三節

真題實例與分析

字元串
【題目描述】
給一個字元串T，問在字元串T中可以包含最多多少個不重疊的字元串S。
字元串中的每個字元為小寫或者大寫字母。
【輸入】
第一行輸入一個字元串S。
第二行輸入一個字元串T。
【輸出】
輸出一行，包括一個整數表示答案。
【樣例輸入】
aba
abababa
【樣例輸出】
2
【數據範圍】
50%的數據，1<=字元串T長度<=20000, 1<=字元串S長度<=100
100%的數據，1<=字元串T長度<=1000000, 1<=字元串S長度<=100000。其中多數是隨機產生。

#include<iostream>
#include<string>
using namespace std;
unsigned long long ha=0,hb=0,k=13331,t=1;
string a,b;
int lena,lenb,ans,last=-1;  
int main(){
    cin>>a>>b;
    lena=a.size();
    lenb=b.size();
    for(int i=0;i<lena;i++){
        ha=ha*k+a[i];
        hb=hb*k+b[i];
        t*=k;
    }
    if(ha==hb){
        ans++;
        last=lena-1;
    }
    for(int i=lena;i<lenb;i++){
        hb=hb*k-b[i-lena]*t+b[i];
        if(ha==hb&&i-lena+1>last){
            ans++;
            last=i;
        }
    }
    cout<<ans;
} 

End.