KMP Algorithm, KMP 字符串搜索算法
Time complexity: O(m+n)
Space complexity: O(m)
Implementation
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <vector> using namespace std; // Author: Huahua namespace KMP { vector<int> Build(const string& p) { const int m = p.length(); vector<int> nxt{0, 0}; for (int i = 1, j = 0; i < m; ++i) { while (j > 0 && p[i] != p[j]) j = nxt[j]; if (p[i] == p[j]) ++j; nxt.push_back(j); } return nxt; } vector<int> Match(const string& s, const string& p) { vector<int> nxt(Build(p)); vector<int> ans; const int n = s.length(); const int m = p.length(); for (int i = 0, j = 0; i < n; ++i) { while (j > 0 && s[i] != p[j]) j = nxt[j]; if (s[i] == p[j]) ++j; if (j == m) { ans.push_back(i - m + 1); j = nxt[j]; } } return ans; } }; // namespace KMP void CheckEQ(const vector<int>& actual, const vector<int>& expected) { if (actual != expected) { std::cout << "expected:"; for (int v : expected) std::cout << " " << v; std::cout << " actual:"; for (int v : actual) std::cout << " " << v; std::cout << std::endl; } else { std::cout << "PASS" << std::endl; } } int main(int argc, char** argv) { CheckEQ(KMP::Build("ABCDABD"), {0, 0, 0, 0, 0, 1, 2, 0}); CheckEQ(KMP::Build("AB"), {0, 0, 0}); CheckEQ(KMP::Build("A"), {0, 0}); CheckEQ(KMP::Build("AA"), {0, 0, 1}); CheckEQ(KMP::Build("AAA"), {0, 0, 1, 2}); CheckEQ(KMP::Build("AABA"), {0, 0, 1, 0, 1}); CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), {15}); CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "AB"), {0, 4, 8, 11, 15, 19}); CheckEQ(KMP::Match("ABC ABCDAB ABCDABCDABDE", "B"), {1, 5, 9, 12, 16, 20}); CheckEQ(KMP::Match("AAAAA", "A"), {0, 1, 2, 3, 4}); CheckEQ(KMP::Match("AAAAA", "AA"), {0, 1, 2, 3}); CheckEQ(KMP::Match("AAAAA", "AAA"), {0, 1, 2}); CheckEQ(KMP::Match("ABC", "ABC"), {0}); return 0; } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#!/usr/bin/env python3 from typing import List # Author: Huahua def Build(p: str) -> List[int]: m = len(p) nxt = [0, 0] j = 0 for i in range(1, m): while j > 0 and p[i] != p[j]: j = nxt[j] if p[i] == p[j]: j += 1 nxt.append(j) return nxt def Match(s: str, p: str) -> List[int]: n, m = len(s), len(p) nxt = Build(p) ans = [] j = 0 for i in range(n): while j > 0 and s[i] != p[j]: j = nxt[j] if s[i] == p[j]: j += 1 if j == m: ans.append(i - m + 1) j = nxt[j] return ans def CheckEQ(actual, expected): if actual != expected: print('actual: %s, expected: %s' % (actual, expected)) else: print('Pass') if __name__ == "__main__": CheckEQ(Build("ABCDABD"), [0, 0, 0, 0, 0, 1, 2, 0]) CheckEQ(Build("AB"), [0, 0, 0]) CheckEQ(Build("A"), [0, 0]) CheckEQ(Build("AA"), [0, 0, 1]) CheckEQ(Build("AAAA"), [0, 0, 1, 2, 3]) CheckEQ(Build("AABA"), [0, 0, 1, 0, 1]) CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "ABCDABD"), [15]) CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "AB"), [0, 4, 8, 11, 15, 19]) CheckEQ(Match("ABC ABCDAB ABCDABCDABDE", "B"), [1, 5, 9, 12, 16, 20]) CheckEQ(Match("AAAAA", "A"), [0, 1, 2, 3, 4]) CheckEQ(Match("AAAAA", "AA"), [0, 1, 2, 3]) CheckEQ(Match("AAAAA", "AAAA"), [0, 1]) CheckEQ(Match("AAAAA", "AAAAA"), [0]) CheckEQ(Match("AABAABA", "AABA"), [0, 3]) |
Applications
LeetCode 28. strStr()
C++
|
1 2 3 4 5 6 7 8 9 |
// Author: Huahua class Solution { public: int strStr(string haystack, string needle) { if (needle.empty()) return 0; auto matches = KMP::Match(haystack, needle); return matches.empty() ? -1 : matches[0]; } }; |
LeetCode 459. Repeated Substring Pattern
C++
|
1 2 3 4 5 6 7 8 9 |
// Author: Huahua class Solution { public: bool repeatedSubstringPattern(string str) { const int n = str.length(); auto nxt = KMP::Build(str); return nxt[n] && nxt[n] % (n - nxt[n]) == 0; } }; |
C++
|
1 2 3 4 5 6 7 |
// Author: Huahua class Solution { public: string longestPrefix(const string& s) { return s.substr(0, KMP::Build(s).back()); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment