{"id":833,"date":"2020-03-22T12:01:22","date_gmt":"2020-03-22T19:01:22","guid":{"rendered":"http:\/\/209.126.2.187\/?p=833"},"modified":"2020-04-12T19:31:47","modified_gmt":"2020-04-13T02:31:47","slug":"kmp","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/22\/kmp\/","title":{"rendered":"KMP"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

In this post, I will introduce some problems related to KMP. <\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 1392<\/a><\/td>Naive Pi<\/td>5-6 points<\/td>\n<\/tr>\n
LC 796<\/a><\/td>Pi on B + \"#\" + A<\/td>3-4 points<\/td>\n<\/tr>\n
LC 214<\/a><\/td>Pi on A + \"#\" + A[::-1]<\/td>5-6 points<\/td>\n<\/tr>\n
LC 28<\/a><\/td>Pi on B + \"#\" + A<\/td>3-4 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

Pi <\/h3>\n\n\n\n

<\/p>\n\n\n\n

  <\/span>   <\/span>\"\[\pi[i] = \max_{k = 0 \dots i}{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]}\]\"<\/p><\/p>\n\n\n\n

\"\pi[i]\" is the length of the longest prefix of substring \"s[0\dots i]\", such that this prefix is also the suffix of \"s[0\dots i]\". Note that this prefix excludes \"s[0\dots i]\" itself. By the definition, we have \"\pi[0] = 0\". For example, we have,<\/p>\n\n\n\n

\"pi("abcabcd") = [0, 0, 0, 1, 2, 3, 0]\"<\/p>\n\n\n\n

\"pi("aabaaab") = [0, 1, 0, 1, 2, 2, 3]\"<\/p>\n\n\n\n

Please refer to this wiki<\/a> if you want to know how the following codes work. <\/p>\n\n\n\n

vector<int> get_pi(string const&s) {\n    int n = s.size();\n    vector<int> pi(n);\n    for (int i = 1; i < n; ++i) {\n        int j = pi[i - 1];\n        while (j > 0 && s[i] != s[j]) {\n            j = pi[j - 1];\n        }\n        pi[i] = j + (s[i] == s[j]);\n    }\n    return pi;\n}<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Summary In this post, I will introduce some problems related to KMP. OJ Details Pi     is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have, Please refer…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,54],"tags":[],"class_list":["post-833","post","type-post","status-publish","format-standard","hentry","category-alg","category-string"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/833","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=833"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/833\/revisions"}],"predecessor-version":[{"id":997,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/833\/revisions\/997"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=833"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=833"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=833"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}