Go 語言實現 Rabin Karp 演算法

---

Go 語言中的 Rabin-Karp 演算法是一種強大的字串搜尋演算法，用於有效地在較大的文字中查詢模式。在本文中，我們需要在 Go 語言中實現 Rabin Karp 演算法，這將能夠有效地進行模式匹配，並展示該演算法在 Go 語言中的靈活性。我們可以使用諸如單函式方法以及使用模組化方法等方法。

模式匹配

假設我們有文字：“ABCABCDABCABC” 和模式 “ABC”，因此透過在 Go 語言中實現 Rabin Karp 演算法，我們可以找出此模式在給定文字字串中重複了多少次以及在何處重複。我們將在下面的示例中瞭解這一點。

單函式方法

此方法利用單個函式在 Go 語言中實現 Rabin Karp 演算法。該函式計算模式的雜湊值，併為文字的滑動視窗生成雜湊值。當雜湊值匹配時，逐字元驗證確認匹配。儘管簡單易懂，但此方法可能不適用於非常大的文字。

模組化方法

模組化方法將演算法劃分為單獨的函式。這些函式管理雜湊計算、滑動期間的雜湊更新以及雜湊衝突期間的字元比較。這種模組化方法更通用，並且在處理大量文字時效能更好。

演算法

• 初始化一個空切片以儲存在文字中找到模式的索引，並計算模式和文字的長度。

• 使用合適的雜湊函式計算模式的雜湊值。從索引 0 到 textLen − patternLen 迭代文字。

• 在迴圈內，計算文本當前子字串的雜湊值。如果子字串的雜湊值與模式的雜湊值匹配

• 在子字串和模式之間執行逐字元比較以驗證匹配。如果確認匹配，則將當前索引附加到索引切片。

• 繼續迭代文字，直到檢查完所有子字串。返回包含找到模式的索引的索引切片。

語法

func rabinKarp(pattern, text string) []int

語法 func rabinKarp(pattern, text string) []int 定義了一個名為 rabinKarp 的函式，該函式接受兩個字串引數 pattern 和 text。該函式返回一個整數切片 ([]int)，表示在文字中找到模式的索引。

func hash(str string) uint64

語法 func hash(str string) uint64 聲明瞭一個名為 hash 的函式，該函式接受一個字串引數 str。該函式旨在返回一個無符號 64 位整數 (uint64)，表示計算出的雜湊值。

示例

在此示例中，我們將使用 Go 語言實現 Rabin Karp 演算法進行模式匹配。rabinKarp 函式以模式和文字作為輸入：pattern 表示我們要搜尋的模式，text 表示我們要在其中搜索模式的文字。在函式內部，實現程式碼處理 Rabin-Karp 演算法。它執行必要的計算和比較以在給定文字中找到模式。然後，該函式返回一個整數切片 []int，其中包含在文字中找到模式的索引。

package main

import (
	"fmt"
)

func rabinKarp(pattern, text string) []int {
	var indices []int
	patternLen := len(pattern)
	textLen := len(text)

	for i := 0; i <= textLen-patternLen; i++ {
		match := true
		for j := 0; j < patternLen; j++ {
			if text[i+j] != pattern[j] {
				match = false
				break
			}
		}
		if match {
			indices = append(indices, i)
		}
	}

	return indices
}

func main() {
	text := "ABCABCDABCABC"
	pattern := "ABC"

	indices := rabinKarp(pattern, text)
	fmt.Println("Pattern found at indices:", indices)
}

輸出

Pattern found at indices: [0 3 7 10]

示例

在此示例中，我們有一個名為 hash 的函式，它接受一個字串引數 str。該函式計算並返回一個無符號 64 位整數 (uint64)，表示輸入字串的雜湊值。在函式內部，實現程式碼使用合適的雜湊演算法計算輸入字串的雜湊值。計算出的雜湊值儲存在 hashValue 變數中並作為無符號 64 位整數 (uint64) 返回。

package main

import (
	"fmt"
)

func hash(str string) uint64 {
	var hashValue uint64

	for i := 0; i < len(str); i++ {
		hashValue += uint64(str[i])
	}

	return hashValue
}

func main() {
	input := "example"

	hashValue := hash(input)
	fmt.Println("Hash value:", hashValue)
}

輸出

Hash value: 748

現實生活中的應用

剽竊檢測

Rabin-Karp 演算法可用於檢測文件中的剽竊行為。透過將每個文件視為一系列字元，並使用該演算法有效地在文件之間搜尋匹配的模式，您可以識別複製內容的例項或文字之間的相似之處。

資料重複資料刪除

在資料儲存系統中，Rabin-Karp 演算法可以幫助識別重複的檔案或資料塊。透過對資料部分進行雜湊處理並使用該演算法比較雜湊值，您可以快速識別兩段資料是否相同或相似。

結論

Rabin-Karp 是一種強大的字串搜尋演算法，可用於檢測剽竊或檔案中重複的資料。在本文中，我們研究瞭如何在 Go 語言中實現 Rabin Karp 演算法，這是一種強大的字串搜尋技術。在這裡，我們探索了兩種方法：直接模式匹配方法和巧妙地使用單獨的雜湊函式。