實現(xiàn) strStr() 函數(shù)
給你兩個字符串 haystack 和 needle ，請你在 haystack 字符串中找出 needle 字符串出現(xiàn)的第一個位置（下標(biāo)從 0 開始）。如果不存在，則返回 -1 。
說明：
當(dāng) needle 是空字符串時，我們應(yīng)當(dāng)返回什么值呢？這是一個在面試中很好的問題。
對于本題而言，當(dāng) needle 是空字符串時我們應(yīng)當(dāng)返回 0 。這與 C 語言的 strstr() 以及 Java 的 indexOf() 定義相符。
示例 1：
輸入：haystack = "hello", needle = "ll"
輸出：2
示例 2：
輸入：haystack = "aaaaa", needle = "bba"
輸出：-1
示例 3：
輸入：haystack = "", needle = ""
輸出：0
提示：
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 僅由小寫英文字符組成
本題是經(jīng)典的字符串單模匹配的模型，因此可以使用字符串匹配算法解決，常見的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等，本文將講解 KMP （Knuth-Morris-Pratt ）算法。
樸素暴力破解法
簡單的循環(huán)判斷即可。
這里用一個 flagArray ， 記錄 needle 每個字符是否在 haystack 中。
代碼
class Solution {
fun strStr(s: String, x: String): Int {
if (x.isEmpty())
return 0
val sArray = s.toCharArray()
val xArray = x.toCharArray()
val width = x.length
for (i in 0..(s.length - 1)) {
if (i + width > s.length) {
break
}
// 針對每一個 i， 遍歷 x
val flagArray = BooleanArray(width, { false })
// 注意: 這地方的區(qū)間 [i, i + width - 1]
(i..(i + width - 1)).forEachIndexed { index, k ->
if (sArray[k] == xArray[index]) {
flagArray[index] = true
}
}
if (flagAllTrue(flagArray)) {
return i
}
}
return -1
}
fun flagAllTrue(flagArray: BooleanArray): Boolean {
var flag = true
flagArray.forEach {
flag = flag && it
}
return flag
}
}
時間復(fù)雜度: O (m * n)
空間復(fù)雜度: O (m)
KMP 算法
KMP 算法的核心思想是在遍歷模式串的過程中，把模式串的對稱前后綴（等綴）部分記錄下來，下一輪比對模式串的時候，直接把上一次已經(jīng)比對的前綴（=后綴）部分跳過，直接來到 next（j）。
動畫圖示：
當(dāng)下標(biāo)為 i=5, j=5 的時候，發(fā)現(xiàn) s[i]!=x[j], 接下來，要開始回溯。
首先，檢查之前已經(jīng)匹配成功的部分：aabaa（ 此時，要看next（4）= 2 ），判斷是否存在相同的「前綴」和「后綴」;
if 存在( 這里是 aa )，則跳轉(zhuǎn)到「前綴」的下一個位置( aabaaf )繼續(xù)往下匹配。
前一個字符的前綴表的數(shù)值是2， 所有把下標(biāo)移動到下標(biāo)2的位置繼續(xù)比配。 可以再反復(fù)看一下上面的動畫。
定義:滑動步長 π(i) 函數(shù)如下：
s[0..i]前后等綴最大長度。
e.g. 模式串：x = aabaaf
π (0) = a = 0
π (1) = aa = 1
π (2) = aab = 0
π (3) = a ab a = 1
π (4) = aabaa = 2
說明一下：比如說，當(dāng)模式串x 跟 s 的第 0..4 個字符均相等，那么如果第 5 個字符不相等，下一輪比對就可以直接從 aa
baa 中的baa 處開始比對了。 因為，前面的aabaa跟后面的aabaa, 在上一輪比對的過程中已經(jīng)匹配過，是相等的。)
π (5) = aabaaf = 0
這個 π(i) 函數(shù)也叫前綴表（prefix table）。前綴表有什么作用呢？ 前綴表是用來回退的，它記錄了模式串與主串(文本串)不匹配的時候，模式串應(yīng)該從哪里開始重新匹配。
實現(xiàn) π(i) 函數(shù) 之后，按照上面動畫演示的算法步驟實現(xiàn)源代碼即可。
如果輸入的模式串為 aabaaf，對應(yīng)的 next 為 0 1 0 1 2 0，（其實這就是前綴表的數(shù)值了）。
那么用這樣的next數(shù)組也可以用來做匹配。實現(xiàn)代碼如下：
class Solution {
fun strStr(s: String, x: String): Int {
val m = x.length
val n = s.length
if (x.isEmpty()) {
return 0
}
var j = 0
// 模式串的最大等綴長度表
val next = getNext(x)
// 遍歷 s[n]
(0..n - 1).forEach {
val i = it
while (j > 0 && s[i] != x[j]) {
j = next[j - 1]
}
if (s[i] == x[j]) {
j++
}
if (j == m) {
return i - m + 1
}
}
return -1
}
fun getNext(s: String): IntArray {
val next = IntArray(s.length)
var j = 0
next[0] = j
for (i in 1 until s.length) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1]
}
if (s[i] == s[j]) {
j++
}
next[i] = j
}
return next
}
}
如何求解前綴函數(shù)？
上面的 getNext(s: String) 函數(shù)的算法思想可以說是“藝術(shù)”了（一般人真的想不到，想必這就是大師為什么是大師了吧?。?/p>
時間復(fù)雜度: O (m + n)
空間復(fù)雜度: O (m)
KMP 算法源代碼
/**
* pi(k) 函數(shù): 遞歸計算字符串的最大公共前后綴的長度 max common prefix suffix length
*/
fun pi(j: Int, pattern: String): Int {
if (j == 0) return 0
for (k in 1 until pattern.length) {
while (pattern[j] != pattern[pi(j - 1, pattern)] && pi(j - 1, pattern) > 0) {
return pi(pi(j - 1, pattern) - 1, pattern)
}
if (pattern[j] == pattern[pi(j - 1, pattern)]) {
return pi(j - 1, pattern) + 1
}
}
return 0
}
fun kmp(text: String, pattern: String): Int {
val m = pattern.length
val n = text.length
if (pattern.isEmpty()) {
return 0
}
// j: the current index of pattern
var j = 0
(0 until n).forEach {
// i: the current index of text
val i = it
while (j > 0 && text[i] != pattern[j]) {
j = pi(j - 1, pattern = pattern)
}
if (text[i] == pattern[j]) {
j++
}
if (j == m) {
return i - m + 1
}
}
return -1
}
fun main() {
var text = "addaabbcaabffffggghhddabcdaaabbbaab"
var pattern = "aabbcaab"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
var index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
text = "hello"
pattern = "ll"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
text = "aaaaa"
pattern = "bba"
for (i in 0 until pattern.length) {
print("${pi(i, pattern)} ")
}
println("\nKMP subtring search algorithm:")
index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")
}
