震驚！世上最接地氣的字符串淺談(HASH+KMP)

筆者過于垃圾，肯定會有些錯的地方，歡迎各位巨佬指正，感激不盡！

引用：LYD的藍書，一本通，DFC的講稿，網上各路巨佬

Luguo id: 章魚那個哥， uid : 87075

Hash

哈希算是除字符串的題，別的什么題用處最多的一種東西了。

干啥子用的：

怎么說呢，就像是給出一個字符串，我們把他化成一個數字。
這樣可以實現快速查詢兩個字符串是否相同，需要 \(O(N)\) 預處理。

咋的寫：

把這個字符串轉換成一個BASE進制數，并對一個模數取模，最好這個模數是一個大質數，這樣對哈希沖突的影響小一點，當然有些時候是合數反而更好。

代碼：

inline int Hash(char s[],int p){int sum=0;for(int i=0;i<(int)strlen(s);++i)sum=(sum*BASE+(int)s[i])%P;return sum%p;
}

小拓展：

雙哈希：

這不是對哈希值哈希，對哈希值哈希會造成更大程度的信息損失。
是對兩個BASE,兩個模數分別做哈希。

樹哈希：

這個分好多種，有對樹形哈希的，有對子樹哈希的。

來看一道NOIP原題:

NOIP-2018對稱二叉樹

發現這題其實就是這個節點的兩個子樹的左序遍歷(Lson,now,Rson)和右序遍歷(Rson,now,Lson)相同時就可以更新答案了，那么我們其實就是要對這棵樹的形狀哈希，那么就可以想到一種辦法：

左兒子，當前點，右兒子附加不同的BASE。

每次更新就可以按照左序右序更新，最后判斷按照左序更新的哈希值和按照右序的哈希值是否一樣就行了

一些應用：

• 可以在 \(O(NlogN)\) 時間內求出一個回文串，可以枚舉中心，二分長度，哈希判斷值

• 可以字符串匹配

• 可以瞎搞(可以參考NOIP-2014解方程)

當然還有后綴排序啥子的，但筆者不會，然而也莫得用到。。。

KMP

干啥子用的：

\(O(N+M)\) 匹配文本串中模式串出現的次數和位置等。

怎么做：

引入nxt[i]表示模式串長度為 \(i\) 時前后綴字符串相同的最長字符。

紅色為已匹配成功的

那么接下來我們發現上面的已匹配的后兩個是和下面的后兩個是匹配的，那么我們不必把模式串指針移動回首位，只需要移動到nxt[失配字符的前一個]，后文中，這個"失配字符的前一個"稱作len。

這樣每次失配就不會浪費時間從頭匹配。

nxt可以自己匹配自己求出來。

代碼

#include<bits/stdc++.h>
using namespace std;int n,m,len;
const int N=1e6+5;
char a[N],b[N];
int nxt[N];int main(){int ans=0;scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);for(int i=2;i<=m;++i){while(len && b[len+1]!=b[i]) len=nxt[len];if(b[len+1]==b[i]) len++;nxt[i]=len;}len=0;for(int i=1;i<=n;++i){while(len && b[len+1]!=a[i]) len=nxt[len];if(b[len+1]==a[i]) len++;if(len==m)ans++,len=nxt[len];}printf("%d\n",ans);for(int i=1;i<=m;++i) printf("%d ",nxt[i]);putchar('\n');return 0;
}

小拓展：

好像莫得，nxt數組倒有些別的用處。

小應用：

可以 \(O(N)\) 求最小循環節長度。考慮如果循環節長度為ans，

那么肯定會有 n-ans=nxt[n]

此篇完結，撒花~~

下一篇——Trie樹和Manacher

轉載于:https://www.cnblogs.com/JCNL666/p/10810271.html

總結

以上是生活随笔為你收集整理的【笔记】震惊！世上最接地气的字符串浅谈(HASH+KMP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。