{"id":6556,"date":"2020-03-31T20:29:45","date_gmt":"2020-04-01T03:29:45","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6556"},"modified":"2020-04-13T20:39:15","modified_gmt":"2020-04-14T03:39:15","slug":"kmp-algorithm-sp19","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sp\/kmp-algorithm-sp19\/","title":{"rendered":"KMP Algorithm SP19"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 KMP Algorithm - \u5237\u9898\u627e\u5de5\u4f5c SP19\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/uKr9qIZMtzw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>KMP Algorithm, KMP \u5b57\u7b26\u4e32\u641c\u7d22\u7b97\u6cd5<\/p>\n\n\n\n<p>Time complexity: O(m+n)<br>Space complexity: O(m)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Implementation<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n#include <iostream>\n#include <vector>\nusing namespace std;\n\n\/\/ Author: Huahua\nnamespace KMP {\nvector<int> Build(const string& p) {\n  const int m = p.length();\n  vector<int> nxt{0, 0};\n  for (int i = 1, j = 0; i < m; ++i) {\n    while (j > 0 && p[i] != p[j])\n      j = nxt[j];\n    if (p[i] == p[j])\n      ++j;\n    nxt.push_back(j);\n  }\n  return nxt;\n}\n\nvector<int> Match(const string& s, const string& p) {\n  vector<int> nxt(Build(p));\n  vector<int> ans;\n  const int n = s.length();\n  const int m = p.length();\n  for (int i = 0, j = 0; i < n; ++i) {\n    while (j > 0 && s[i] != p[j])\n      j = nxt[j];\n    if (s[i] == p[j])\n      ++j;\n    if (j == m) {\n      ans.push_back(i - m + 1);\n      j = nxt[j];\n    }\n  }\n  return ans;\n}\n};  \/\/ namespace KMP\n\nvoid CheckEQ(const vector<int>& actual, const vector<int>& expected) {\n  if (actual != expected) {\n    std::cout << \"expected:\";\n    for (int v : expected)\n      std::cout << \" \" << v;\n    std::cout << \" actual:\";\n    for (int v : actual)\n      std::cout << \" \" << v;\n    std::cout << std::endl;\n  } else {\n    std::cout << \"PASS\" << std::endl;\n  }\n}\n\nint main(int argc, char** argv) {\n  CheckEQ(KMP::Build(\"ABCDABD\"), {0, 0, 0, 0, 0, 1, 2, 0});\n  CheckEQ(KMP::Build(\"AB\"), {0, 0, 0});\n  CheckEQ(KMP::Build(\"A\"), {0, 0});\n  CheckEQ(KMP::Build(\"AA\"), {0, 0, 1});\n  CheckEQ(KMP::Build(\"AAA\"), {0, 0, 1, 2});\n  CheckEQ(KMP::Build(\"AABA\"), {0, 0, 1, 0, 1});\n  CheckEQ(KMP::Match(\"ABC ABCDAB ABCDABCDABDE\", \"ABCDABD\"), {15});\n  CheckEQ(KMP::Match(\"ABC ABCDAB ABCDABCDABDE\", \"AB\"), {0, 4, 8, 11, 15, 19});\n  CheckEQ(KMP::Match(\"ABC ABCDAB ABCDABCDABDE\", \"B\"), {1, 5, 9, 12, 16, 20});\n  CheckEQ(KMP::Match(\"AAAAA\", \"A\"), {0, 1, 2, 3, 4});\n  CheckEQ(KMP::Match(\"AAAAA\", \"AA\"), {0, 1, 2, 3});\n  CheckEQ(KMP::Match(\"AAAAA\", \"AAA\"), {0, 1, 2});\n  CheckEQ(KMP::Match(\"ABC\", \"ABC\"), {0});\n  return 0;\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\n#!\/usr\/bin\/env python3\nfrom typing import List\n\n# Author: Huahua\n\n\ndef Build(p: str) -> List[int]:\n    m = len(p)\n    nxt = [0, 0]\n    j = 0\n    for i in range(1, m):\n        while j > 0 and p[i] != p[j]:\n            j = nxt[j]\n        if p[i] == p[j]:\n            j += 1\n        nxt.append(j)\n    return nxt\n\n\ndef Match(s: str, p: str) -> List[int]:\n    n, m = len(s), len(p)\n    nxt = Build(p)\n    ans = []\n    j = 0\n    for i in range(n):\n        while j > 0 and s[i] != p[j]:\n            j = nxt[j]\n        if s[i] == p[j]:\n            j += 1\n        if j == m:\n            ans.append(i - m + 1)\n            j = nxt[j]\n    return ans\n\n\ndef CheckEQ(actual, expected):\n    if actual != expected:\n        print('actual: %s, expected: %s' % (actual, expected))\n    else:\n        print('Pass')\n\n\nif __name__ == \"__main__\":\n    CheckEQ(Build(\"ABCDABD\"), [0, 0, 0, 0, 0, 1, 2, 0])\n    CheckEQ(Build(\"AB\"), [0, 0, 0])\n    CheckEQ(Build(\"A\"), [0, 0])\n    CheckEQ(Build(\"AA\"), [0, 0, 1])\n    CheckEQ(Build(\"AAAA\"), [0, 0, 1, 2, 3])\n    CheckEQ(Build(\"AABA\"), [0, 0, 1, 0, 1])\n    CheckEQ(Match(\"ABC ABCDAB ABCDABCDABDE\", \"ABCDABD\"), [15])\n    CheckEQ(Match(\"ABC ABCDAB ABCDABCDABDE\", \"AB\"), [0, 4, 8, 11, 15, 19])\n    CheckEQ(Match(\"ABC ABCDAB ABCDABCDABDE\", \"B\"), [1, 5, 9, 12, 16, 20])\n    CheckEQ(Match(\"AAAAA\", \"A\"), [0, 1, 2, 3, 4])\n    CheckEQ(Match(\"AAAAA\", \"AA\"), [0, 1, 2, 3])\n    CheckEQ(Match(\"AAAAA\", \"AAAA\"), [0, 1])\n    CheckEQ(Match(\"AAAAA\", \"AAAAA\"), [0])\n    CheckEQ(Match(\"AABAABA\", \"AABA\"), [0, 3])\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Applications<\/strong><\/h2>\n\n\n\n<p>LeetCode 28. strStr()<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\/\/ Author: Huahua\nclass Solution {\npublic:\n  int strStr(string haystack, string needle) {\n    if (needle.empty()) return 0;\n    auto matches = KMP::Match(haystack, needle);\n    return matches.empty() ? -1 : matches[0];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>LeetCode 459.&nbsp;Repeated Substring Pattern<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\/\/ Author: Huahua\nclass Solution {\npublic:\n  bool repeatedSubstringPattern(string str) {\n    const int n = str.length();\n    auto nxt = KMP::Build(str);\n    return nxt[n] &amp;&amp; nxt[n] % (n - nxt[n]) == 0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><a href=\"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1392-longest-happy-prefix\/\">1392.&nbsp;Longest Happy Prefix<\/a><\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre>\/\/ Author: Huahua\nclass Solution {\npublic:\n  string longestPrefix(const string&amp; s) {    \n    return s.substr(0, KMP::Build(s).back());\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>KMP Algorithm, KMP \u5b57\u7b26\u4e32\u641c\u7d22\u7b97\u6cd5 Time complexity: O(m+n)Space complexity: O(m) Implementation #include #include using namespace std; \/\/ Author: Huahua namespace KMP { vector Build(const string&#038; p)&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[170],"tags":[572,97,374,186],"class_list":["post-6556","post","type-post","status-publish","format-standard","hentry","category-sp","tag-kmp","tag-prefix","tag-sp","tag-suffix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6556","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6556"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6556\/revisions"}],"predecessor-version":[{"id":6615,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6556\/revisions\/6615"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}