February 04, 2023

Leetcode | Algorithm - KMP

Notes: KMP (Knuth Morris Pratt). reference here.

Introduction

字串尋找演算法 (KMP), 可在一個字串中尋找另一個字串的出現位子, 使用這個算法的平均時間複雜度是 O(n+m), 其中 n 為字串的長度, m 為模式串的長度.

Brute Force

我們先看看暴力解如何去解，假設有兩個字串:

text: “aabaabaaf”
pattern: “aabaaf”

最值觀的寫法就是從 text 開始做 for loop, 接下來逐字匹配 text, 如果 pattern 找到匹配失敗的 text 才往前移動 1 直到能將 pattern 匹配完或者 traverse text 結束. 在這種寫法下時間複雜度為 O(m*n), 因為至少每個 text 的 element 都要經過一次 pattern 的匹配過程. 也可以想像成一個滑動的窗口, 窗口的大小為 pattern size.

28. Find the Index of the First Occurrence in a String 中的暴力解法.

func strStr(haystack string, needle string) int {
	var result int = -1
	if len(haystack) < len(needle) {
		return result
	}
	for i := 0; i < len(haystack); i++ {
		if checkStr(haystack, needle, i) {
			result = i
			return result
		}
	}
	return result
}

func checkStr(haystack, needle string, index int) bool {
	for i := 0; i <= len(needle); i++ {
		if i == len(needle) {
			return true
		}
		if index >= len(haystack) {
			return false
		}
		if haystack[index] == needle[i] {
			index++
		} else {
			return false
		}
	}
	return false
}