題目來源

28. 找出字符串中第一個匹配項的下標 - 力扣（LeetCode）

題目解析

暴力解法

本題如果采用暴力解法的話，可以定義兩個指針 i，j，其中 i 指針用于掃描 S（haystack）串，j 指針用于掃描 T（needle）串。

比如：S = "aabaabaaf"，T = "aabaaf"

假設 S 串的起始匹配位置為 k，則 k 取值范圍是：[0, s.length - t.length]

上圖匹配過程中，分為兩個循環：

外層循環，即匹配的輪數控制，或者說是，S串的匹配起始位置控制，比如：

• 第 0 輪，T 串是從 S 串的 0 索引位置開始匹配
• 第 1 輪，T 串是從 S 串的 1 索引位置開始匹配
• ...
• 第 k 輪，T 串是從 S 串的 k 索引位置開始匹配

內層循環，即T串和S串的 k ~ k + t.length 范圍進行逐個字符一一匹配，

• 如果發現存在對應位的字符不一致，則說明當前輪匹配失敗，直接進入下一輪
• 如果所有位置上的字符都相同，則說明匹配成功，即在S中找到了和T相同的子串，且該子串起始位置是k

假設，s.length = n，t.length = m，則暴力解法的時間復雜度為O(n * m)

KMP算法

對于字符串模式匹配問題，暴力算法并非最優解決方案，雖然 s，t 都是隨機串，但是這些隨機串也會存在一定規律可以利用。

比如上面暴力解法圖示中，當第 k = 0 輪匹配失敗后，第 k =1 輪，第 k =2 輪是否注定失敗了呢？

如下圖是第 k = 0 輪最后一個字符匹配失敗的情況：

我們觀察其中匹配成功的部分，即"aabaa"部分，這部分具有相同前后綴aa。

如果我們將 S，T 的?"aabaa" 后面部分抽象化（....），如下圖所示，那么：

• 第 k = 0 輪匹配失敗是因為 “抽象部分（....）” 的匹配失敗
  
  
• 第 k = 1 輪，第 k = 2 輪匹配失敗，其實就是 "aabaa" 部分的匹配失敗：
  
  

?我們將第 k = 1 輪，第 k = 2 輪，第 k = 3 輪再次簡化一下，如下圖所示：

那么是不是很顯然可以發現，第1輪，第2輪是注定失敗的。

我們再舉一個例子：

如果上面 S，T 在第 k = 0 輪因為抽象部分（...）匹配失敗，那么下一輪，其實是否可以直接讓：前綴部分直接跳轉到后綴位置？

因為前綴部分（如abc）和后綴部分（如abc）完全相同，而前綴部分（如abc）和中間部分（如d）不相同，因此前綴部分（如abc）和中間部分對齊（如d）時，必然匹配失敗。

這樣的話，是不是跳過了兩輪匹配，即節省了兩輪匹配的時間。

請大家再思考一下，上面讓前綴部分直接跳轉和后綴部分對齊，真的是只節省兩輪匹配的過程嗎？

下面圖示是，第0輪匹配失敗后，直接跳到對稱部分開始重新匹配

如果對應到暴力解法過程的話，那么下面畫X的部分就都是跳過的過程

我們再觀察下這個跳到對稱部分的過程中，i，j指針的變化

可以發現，i 指針在 S 中的位置并沒有改變

• j 指針回退指向到了 T 的 "aabaa" 前綴部分（aa）的后一個位置（b所在位置）
• 或者假設前綴部分（aa）長度為 len，則 j 回退到 T 串的 len 索引位置

那么上面這個改進算法的時間復雜度是多少呢？

由于上面算法中，保證了 i 指針不會回退，因此時間復雜度只有O(n)。

而這個算法其實就是KMP算法。

前綴表概念

上面我們已經說明了KMP算法的大致原理，其中最關鍵的就是在模式串 T 中找其前綴子串的最長相同前后綴，比如

T = "aabaaf" 有前綴子串 "aabaa"，該子串的最長相同前后綴是 "aa"

那么該如何通過代碼來實現這個功能呢？

KMP算法的三個創始人K，M，P提出了前綴表的概念。

首先定義下字符串的前綴、后綴概念

假設字符串 t 長度為n，那么：

• 前綴就是起始索引必須為0，結束索引＜n-1的所有子串
• 后綴就是結束索引必須為n-1，起始索引必須>0的所有子串

因此

• 前綴和后綴不能是字符串 t 本身
• 字符串 t 的前綴和后綴是可能存在重疊部分的

我們舉一個例子，比如列出T的子串 "aabaa" 的所有的前綴和后綴

長度	前綴（紅色子串）	后綴（綠色子串）
1	aabaa	aabaa
2	aabaa	aabaa
3	aabaa	aabaa
4	aabaa	aabaa

其中最長且相同的前后綴是"aa"。

注意，判斷前綴和后綴是否相同，都是從左往右逐一比對，因此上面例子中，長度為3的前綴"aab"和后綴"baa"是不相同的。

還有相同的前綴、后綴是可能存在重疊

比如字符串 "ababab"

長度	前綴（紅色子串）	后綴（綠色子串）
1	ababab	ababab
2	ababab	ababab
3	ababab	ababab
4	ababab	ababab
5	ababab	ababab

最長相同的前綴和后綴是"abab"?，他們是存在重疊的

因此T = "aabaaf"所有前綴子串的最長相同的前綴和后綴的長度分別為：

T的前綴串	最長相同的前后綴	最長相同的前后綴的長度
a	""	0
aa	a	1
aab	""	0
aaba	a	1
aabaa	aa	2
aabaaf	""	0

我們將 T 的所有前綴串對應的 “最長相同的前后綴的長度” 記錄為一個數組 next，我們稱 next 為前綴表

next = [0, 1, 0, 1, 2, 0]

前綴表的應用

前面我們手算出了前綴表 next 數組

next = [0, 1, 0, 1, 2, 0]

next[j] 表示：T 的 [0, j]?范圍子串的最長相同前后綴長度，比如：

• next[0] 表示：T的 [0,0] 范圍子串 "a"? ? ? ? ? 的最長相同前后綴長度 0
• next[1] 表示：T的 [0,1] 范圍子串 "aa"? ? ? ? 的最長相同前后綴長度 1
• next[2] 表示：T的 [0,2] 范圍子串 "aab"? ? ? 的最長相同前后綴長度 0
• next[3] 表示：T的 [0,3] 范圍子串 "aaba"? ? 的最長相同前后綴長度 1
• next[4] 表示：T的 [0,4] 范圍子串 "aabaa"? 的最長相同前后綴長度 2
• next[5] 表示：T的 [0,5] 范圍子串 "aabaaf" 的最長相同前后綴長度 0

那么如何將 next 應用到KMP算法中呢？

比如下圖中，S[i] != T[j] 時，我們前面分析過，需要做如下動作：

• i 指針保持指向不變
• j 指針回退到 T 的 len 索引位置（len：表示 T 的前綴串 "aabaa" 的最長相同前后綴 "aa" 的長度）

len 含義和 next[j-1] 含義是相同的

• next[j - 1] 表示 T 的 [0, j-1] 范圍子串 "aabaa" 的最長相同前后綴的長度?

因此，當s[i] != t[j] 時，我們可以讓： j = next[ j - 1 ]

另外，如果 j = 0 時就匹配不上，此時 next[j-1] 會發生越界異常，因此針對這種i情況，我們應該特殊處理，如下圖所示，就是一個 j = 0無法匹配的情況：

此時，我們應該讓 i++，j 保持不變，繼續匹配

這其實和前面KMP算法規定的 i 指針不回退這一條件不沖突。因為上面過程 i 指針沒有發生回退。

生成前綴表

前面我們已經手算過了前綴表，但是手算過程是一個暴力枚舉的過程。

關于前綴表的生成，我們可以利用動態規劃求解。

比如：假設已知 K = NEXT[J-1]，現在要求 NEXT[J]，比如下圖

如果 T[J] == T[K] 的話，比如

NEXT[J] 表示 [0, J] 范圍子串 "abdabeabdabe" 的最長相同前后綴（"abdabe"）長度為 K+1

因此當 T[J] == T[K] 時，那么 NEXT[J]? = K + 1

如果T[J] ! = T[K]的話，比如

那么此時該如何求解 NEXT[J] 呢？

我們將上圖繼續分解

如果下面兩個位置的字符相同

那么此時就找到了 NEXT[J] 的值。

因此當 T[J] != T[K] 時，我們可以讓 K = NEXT[K-1]，繼續前面邏輯，直到 K 移動到：

• T[J] == T[K] 時，此時 NEXT[J] = K + 1
• 若 K == 0 時，依舊 T[J] != T[K]，則此時可以認為 NEXT[J] = 0，此時我們J++，求解下一個 NEXT[J]

C算法源碼

暴力解法

int strStr(char* s, char* t) {int sLen = strlen(s);int tLen = strlen(t);for (int k = 0; k <= sLen - tLen; k++) {int i = k;int j = 0;while (j < tLen && s[i] == t[j]) {i++;j++;}if (j == tLen) {return k;}}return -1;
}

KMP算法

int* getNext(char* t) {int tLen = strlen(t);int* next = (int*)calloc(tLen, sizeof(int));int j = 1;int k = next[j - 1];while (j < tLen) {if (t[j] == t[k]) {next[j] = k + 1; // 前綴范圍 t[0,k] == 后綴范圍 t[j-k,j]  此時最長相同前后綴長度為：k+1j++;k++;} else if (k > 0) {k = next[k - 1]; // 若 t[j] != t[k] && k > 0，則縮短前綴部分，k = next[k-1] 后繼續比較 t[k] 和 t[j]} else {j++; // 若 t[j] != t[k] && k == 0，則 k 無法繼續后退，此時可以認為 next[j] 為 0，進行j++，繼續求解下一個next[j]}}return next;
}int strStr(char* s, char* t) {int sLen = strlen(s);int tLen = strlen(t);int* next = getNext(t); // 生成 t 串的前綴表int i = 0;int j = 0;while (i < sLen && j < tLen) {if (s[i] == t[j]) {i++;j++;} else if (j > 0) {j = next[j - 1]; // 若 s[i] != t[j] && j > 0，則 i 指針不動，j 指針回退到 t 串的 next[j-1] 位置 } else {i++; // 若 s[i] != t[j] && j == 0，則表示 s[i] 和 t[0] 首個字符就匹配失敗，我們只能進入下一輪，即 i++}}if (j == tLen) { // 若 t 串所有字符都被匹配成功，則 j == t.lengthreturn i - j; // 此時 s 串的 i - j 位置就是首次匹配 t 的子串起始位置} else {return -1;}
}

C++算法源碼

暴力解法

class Solution {
public:int strStr(string s, string t) {int sLen = s.size();int tLen = t.size();for (int k = 0; k <= sLen - tLen; k++) {int i = k;int j = 0;while (j < tLen && s[i] == t[j]) {i++;j++;}if (j == tLen) {return k;}}return -1;}
};

KMP算法

class Solution {
public:int strStr(string s, string t) {vector<int> next = getNext(t); // 生成 t 串的前綴表int i = 0;int j = 0;while (i < s.size() && j < t.size()) {if (s[i] == t[j]) {i++;j++;} else if (j > 0) {j = next[j - 1]; // 若 s[i] != t[j] && j > 0，則 i 指針不動，j 指針回退到 t 串的 next[j-1] 位置 } else {i++; // 若 s[i] != t[j] && j == 0，則表示 s[i] 和 t[0] 首個字符就匹配失敗，我們只能進入下一輪，即 i++}}if (j == t.size()) { // 若 t 串所有字符都被匹配成功，則 j == t.lengthreturn i - j; // 此時 s 串的 i - j 位置就是首次匹配 t 的子串起始位置} else {return -1;}}vector<int> getNext(string t) {vector<int> next(t.size(), 0);int j = 1;int k = next[j - 1];while (j < t.size()) {if (t[j] == t[k]) {next[j] = k + 1;  // 前綴范圍 t[0,k] == 后綴范圍 t[j-k,j]  此時最長相同前后綴長度為：k+1j++;k++;} else if (k > 0) {k = next[k - 1]; // 若 t[j] != t[k] && k > 0，則縮短前綴部分，k = next[k-1] 后繼續比較 t[k] 和 t[j]} else {j++; // 若 t[j] != t[k] && k == 0，則 k 無法繼續后退，此時可以認為 next[j] 為 0，進行j++，繼續求解下一個next[j]}}return next;}
};

Java算法源碼

暴力解法

class Solution {public int strStr(String haystack, String needle) {char[] s = haystack.toCharArray();char[] t = needle.toCharArray();for (int k = 0; k <= s.length - t.length; k++) {int i = k;int j = 0;while (j < t.length && s[i] == t[j]) {i++;j++;}if (j == t.length) {return k;}}return -1;}
}

KMP算法

class Solution {public int strStr(String haystack, String needle) {char[] s = haystack.toCharArray();char[] t = needle.toCharArray();int[] next = getNext(t); // 生成 t 串的前綴表int i = 0;int j = 0;while (i < s.length && j < t.length) {if (s[i] == t[j]) {i++;j++;} else if (j > 0) { // 若 s[i] != t[j] && j > 0，則 i 指針不動，j 指針回退到 t 串的 next[j-1] 位置 j = next[j - 1];} else { // 若 s[i] != t[j] && j == 0，則表示 s[i] 和 t[0] 首個字符就匹配失敗，我們只能進入下一輪，即 i++i++;}}if (j == t.length) { // 若 t 串所有字符都被匹配成功，則 j == t.lengthreturn i - j; // 此時 s 串的 i - j 位置就是首次匹配 t 的子串起始位置} else {return -1;}}public static int[] getNext(char[] t) {int[] next = new int[t.length];int j = 1;int k = next[j-1];while (j < t.length) {if (t[j] == t[k]) {next[j] = k + 1; // 前綴范圍 t[0,k] == 后綴范圍 t[j-k,j]  此時最長相同前后綴長度為：k+1j++;k++;} else if (k > 0) { // 若 t[j] != t[k] && k > 0，則縮短前綴部分，k = next[k-1] 后繼續比較 t[k] 和 t[j]k = next[k - 1];} else {j++; // 若 t[j] != t[k] && k == 0，則 k 無法繼續后退，此時可以認為 next[j] 為 0，進行j++，繼續求解下一個next[j]}}return next;}
}

Python算法源碼

暴力解法

class Solution(object):def strStr(self, s, t):""":type haystack: str:type needle: str:rtype: int"""for k in range(0, len(s) - len(t) + 1):i = kj = 0while j < len(t) and s[i] == t[j]:i += 1j += 1if j == len(t):return kreturn -1

KMP算法

def getNext(t):next = [0] * len(t)j = 1k = next[j - 1]while j < len(t):if t[j] == t[k]:next[j] = k + 1  # 前綴范圍 t[0,k] == 后綴范圍 t[j-k,j]  此時最長相同前后綴長度為：k+1j += 1k += 1elif k > 0:k = next[k - 1]  # 若 t[j] != t[k] && k > 0，則縮短前綴部分，k = next[k-1] 后繼續比較 t[k] 和 t[j]else:j += 1  # 若 t[j] != t[k] && k == 0，則 k 無法繼續后退，此時可以認為 next[j] 為 0，進行j++，繼續求解下一個next[j]return nextclass Solution(object):def strStr(self, s, t):""":type haystack: str:type needle: str:rtype: int"""next = getNext(t)  # 生成 t 串的前綴表i, j = 0, 0while i < len(s) and j < len(t):if s[i] == t[j]:i += 1j += 1elif j > 0:j = next[j - 1]  # 若 s[i] != t[j] && j > 0，則 i 指針不動，j 指針回退到 t 串的 next[j-1] 位置 else:i += 1  # 若 s[i] != t[j] && j == 0，則表示 s[i] 和 t[0] 首個字符就匹配失敗，我們只能進入下一輪，即 i++if j == len(t):  # 若 t 串所有字符都被匹配成功，則 j == t.lengthreturn i - j  # 此時 s 串的 i - j 位置就是首次匹配 t 的子串起始位置else:return -1

JavaScript算法源碼

暴力解法

/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function (s, t) {for (let k = 0; k <= s.length - t.length; k++) {let i = k;let j = 0;while (j < t.length && s[i] == t[j]) {i++;j++;}if (j == t.length) {return k;}}return -1;
};

KMP算法

/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function (s, t) {const next = getNext(t); // 生成 t 串的前綴表let i = 0;let j = 0;while (i < s.length && j < t.length) {if (s[i] == t[j]) {i++;j++;} else if (j > 0) {j = next[j - 1]; // 若 s[i] != t[j] && j > 0，則 i 指針不動，j 指針回退到 t 串的 next[j-1] 位置} else {i++; // 若 s[i] != t[j] && j == 0，則表示 s[i] 和 t[0] 首個字符就匹配失敗，我們只能進入下一輪，即 i++}}if (j == t.length) { // 若 t 串所有字符都被匹配成功，則 j == t.lengthreturn i - j; // 此時 s 串的 i - j 位置就是首次匹配 t 的子串起始位置} else {return -1;}
};var getNext = function (t) {const next = new Array(t.length).fill(0);let j = 1;let k = next[j - 1];while (j < t.length) {if (t[j] == t[k]) {next[j] = k + 1; // 前綴范圍 t[0,k] == 后綴范圍 t[j-k,j]  此時最長相同前后綴長度為：k+1j++;k++;} else if (k > 0) {k = next[k - 1]; // 若 t[j] != t[k] && k > 0，則縮短前綴部分，k = next[k-1] 后繼續比較 t[k] 和 t[j]} else {j++; // 若 t[j] != t[k] && k == 0，則 k 無法繼續后退，此時可以認為 next[j] 為 0，進行j++，繼續求解下一個next[j]}}return next;
}