KMP Algorithm, KMP 字符串搜索算法

Time complexity: O(m+n)
Space complexity: O(m)

Implementation

C++

#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

#!/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++

// 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++

// 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;

}

};

1392. Longest Happy Prefix

C++

// Author: Huahua

class Solution {

public:

string longestPrefix(const string& s) {

return s.substr(0, KMP::Build(s).back());

}

};

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

"""

Returns the smallest number m such that g(m) is true.

"""

def binary_search(l, r):

while l < r:

m = l + (r - l) // 2

if f(m): return m # if m is the answer

if g(m):

r = m # new range [l, m)

else

l = m + 1 # new range [m+1, r)

return l # or not found

Slides:

Lower Bound / Upper Bound

#include <iostream>

#include <vector>

using namespace std;

int upper_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > val)

r = m;

else

l = m + 1;

}

return l;

}

int lower_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] >= val)

r = m;

else

l = m + 1;

}

return l;

}

int main() {

vector<int> A{1, 2, 2, 2, 4, 4, 5};

cout << lower_bound(A, 0, 0, A.size()) << endl; // 0

cout << lower_bound(A, 2, 0, A.size()) << endl; // 1

cout << lower_bound(A, 3, 0, A.size()) << endl; // 4

cout << upper_bound(A, 2, 0, A.size()) << endl; // 4

cout << upper_bound(A, 4, 0, A.size()) << endl; // 6

cout << upper_bound(A, 5, 0, A.size()) << endl; // 7

}

Posts tagged as “sp”

KMP Algorithm SP19

Implementation

C++

Python3

Applications

C++

C++

C++

花花酱 Binary Search II SP17

花花酱 LeetCode Binary Trees 二叉树 SP12

花花酱 SP5 Binary Search

Mentioned Problems