Can you summarize the following document?
        
  下文中設所有模式串長為m,所有文字串長為n。  要在給定文字中搜尋模式串,最簡單的樸素演算法的做法是將模式串與文字中所有位置進行比對。每次比對所需時間為formula_1,所有可能的位置數為m,故該演算法的最壞複雜度為formula_2。一種典型的優化為:當匹配到文字串的某一位置時,若文字串與模式串在任一位置失配,則直接移動到下一個位置繼續嘗試匹配。這種優化省去了在已經確定當前位置文字串失配時剩餘的無用匹配嘗試,但在特定情況下它無法確保任何加速。相對地,  一些字串匹配演算法會利用失配時的資訊來降低最壞情況複雜度:每次失配時,文字的當前位置會使得兩串中至少存在一處不同,這使得上述演算法可以跳過已經確定無法成功匹配的位置。這類演算法中KMP演算法與Boyer-Moore字串搜尋演算法較為常見。本條目所述的演算法的加速方式則不同:此演算法使用雜湊函式以快速對每個位置能否匹配作大致的檢測,此後只對通過了檢測的位置進行匹配嘗試。  字串搜尋中所用雜湊函式(或雜湊函式)會對每一個字串進行處理與計算,生成的數值稱為雜湊值(或雜湊值):例如,在以某種方式定義了雜湊函式hash()後,我們可能有hash(rabin)=2020,hash("karp")=2019(僅供示意)。如果兩個字串相等,那麼它們的雜湊值相等。對於一些良好的雜湊函式而言,通常情況下這句話反之依然成立:不同的字串在大多數情況下擁有不同的雜湊值。此演算法會在文字串的每一個位置計算從該位置開始的、與模式串等長的子串的雜湊值;如果該值與模式串的雜湊值相等,則演算法會在該位置進行模式串的遍歷比較。  為使此演算法正常並且良好地工作,雜湊函式應從不易產生偽陽性錯誤的函式中隨機挑選以防止非匹配位置的字串雜湊值與模式串相同,從而增加並沒有對匹配產生貢獻的冗餘運算量。另外,所採用的雜湊函式應當為旋轉雜湊(特點為新位置的雜湊值可以通過已有雜湊值快速計算)以防止重新計算的額外工作。

  演算法實現如下。  function RabinKarp(string s[1..n], string pattern[1..m])  第2/4/6行中每行執行一次時間複雜度均為formula_3,但第2行只被執行一次,第6行僅在雜湊值相等時被執行(次數也因此較少)。在被執行了n次的第5行中,由於雜湊值的比較僅需常數時間,其對複雜度的影響為formula_1。演算法時間複雜度的瓶頸在於第四行。  用樸素演算法計算雜湊值時,由於每一個字元都需計算,共需要formula_3的複雜度。由於在每一次迴圈時均需要計算及比較雜湊值,採用此方法時演算法總複雜度退化為formula_2(與樸素演算法無異)。若要提速,每次進行雜湊值計算時,其複雜度不應超過常數時間。由於每次計算雜湊值時,已有上一個位置的雜湊值為基礎,倘若能用以在常數時間內計算新位置的雜湊值,則總時間將急遽減少。因此,我們引入旋轉雜湊。  旋轉雜湊是一種專為此操作設計的雜湊演算法。一種便捷但並不優秀的旋轉雜湊函式採用的計算方法為直接減去串首字元的值並減去串尾字元的值:  此類函式可以在常數時間內計算模式串移動時的雜湊值,但由於雜湊演算法並不好,其將會使第5行與採用其他更復雜的雜湊函式(如下文)時相比被過多執行。一個良好的雜湊演算法不應產生過多相同的雜湊值,因其會使比較次數增加(極端情況時,若所有字串的雜湊值均相同,其最壞情況複雜度與不加優化時相同,為formula_2。

  對於Rabin–Karp演算法,一種常用的可靠、高效的雜湊演算法為。在此處敘述的演算法並非Rabin指紋,但依然有良好的表現。本演算法視字串中的每一個子串為某進位制下的一個數字,通常進位制數與字符集大小相同。  例:若子串為"hi",字符集大小/進製為256,用於取模的質數為101,那麼雜湊值將會以如下方式計算(此處採用字元的ASCII值):  [(104 × 256 ) % 101 + 105] % 101 = 65  與一般的進位制不同的是,所用進位制可以比某一位上的數字大,詳見雜湊函式。使用此類雜湊函式的最大優勢在於可以僅需常數次操作或計算來得到新位置的雜湊值。例如,當文字串為"abracadabra"、模式串長為3、首個可能的匹配的串為"abr"、進位制數為256、用於取模的質數為101時,其雜湊值以如下方式計算:  若要從上一個串的雜湊值4計算下一個串"bra"的雜湊值,只需減去首字母a的雜湊值(需乘上對應偏移量,即該位置字母在當前串中所乘進位制數的冪,本例為97 × 256),將整個串偏移一位(即乘上進位制數)再加上新的末位字母對應雜湊值(本例為97 × 256)即可:  此雜湊值與直接計算時結果相同:  但當模式串較長時,其能極大地節約時間。  理論上仍有其他能實現便捷計算的雜湊演算法,如取所有字元的ASCII乘積為雜湊值等。此種雜湊演算法的限制在於資料型別的上限與取模的必要性,參考雜湊函式。而另一些雜湊演算法,要麼耗時較長,要麼較容易產生雜湊衝突而因此減慢了演算法執行的速度。因此,本節所記雜湊演算法通常被Rabin–Karp演算法採用。

  Rabin–Karp演算法在單模式搜尋方面不如Knuth–Morris–Pratt演算法、Boyer-Moore字串搜尋演算法和其他較快的單模式字串搜尋演算法,因為它的最壞情況行為很慢。然而,它是多模式搜尋的首選演算法。  為了在文字中找到任何一個大量的,比如說"k"個固定長度的模式,Rabin–Karp演算法的一個簡單變體使用布隆過濾器或集合資料結構來檢查給定字串的雜湊值是否屬於我們要尋找的模式的雜湊值集合:  function RabinKarpSet(string s[1..n], set of string subs, m):  我們假設所有子串都具有固定長度"m" 。 一種樸素的搜尋"k"個模式的方法是,重複每次花費O("n+m")時間的單模式搜尋,總時間為O("(n+m)k")。 與之對比,假設雜湊表檢查工作在O(1)預期時間內,那麼上述演算法可以在O("n"+"km")個預期時間內找到所有"k"個模式。一個確定性的"O"("n"+"km")解就是Aho-Corasick演算法。
在電腦科學中,Rabin–Karp演算法或Karp–Rabin演算法(英文:Rabin–Karp algorithm或Karp–Rabin algorithm),是一種由理查德·卡普與邁克爾·拉賓於1987年提出的、使用雜湊函式以在文字中搜尋單個模式串的字串搜尋演算法單次匹配。該演算法先使用旋轉雜湊以快速篩出無法與給定串匹配的文字位置,此後對剩餘位置能否成功匹配進行檢驗。此演算法可推廣到用於在文字搜尋單個模式串的所有匹配或在文字中搜尋多個模式串的匹配。