{"id":86345,"date":"2020-05-14T12:52:20","date_gmt":"2020-05-14T04:52:20","guid":{"rendered":"http:\/\/4563.org\/?p=86345"},"modified":"2020-05-14T12:52:20","modified_gmt":"2020-05-14T04:52:20","slug":"kmp-%e9%87%8c%e9%9d%a2%e7%9a%84%e9%83%a8%e5%88%86%e5%8c%b9%e9%85%8d%e8%a1%a8%e6%9e%84%e9%80%a0%e5%93%aa%e4%bd%8d%e8%83%bd%e8%a7%a3%e9%87%8a%e4%b8%80%e4%b8%8b%e7%ac%ac%e4%ba%8c%e5%b1%82%e7%9a%84","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=86345","title":{"rendered":"KMP \u91cc\u9762\u7684\u90e8\u5206\u5339\u914d\u8868\u6784\u9020\u54ea\u4f4d\u80fd\u89e3\u91ca\u4e00\u4e0b\u7b2c\u4e8c\u5c42\u7684\u5faa\u73af\u5417\uff1f"},"content":{"rendered":"
\n
\n
\n

KMP \u91cc\u9762\u7684\u90e8\u5206\u5339\u914d\u8868\u6784\u9020\u54ea\u4f4d\u80fd\u89e3\u91ca\u4e00\u4e0b\u7b2c\u4e8c\u5c42\u7684\u5faa\u73af\u5417\uff1f <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : qwertyegg <\/span> <\/i> 7<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n
fun partialMatchTable(pattern: String): IntArray{     var pmt = IntArray(pattern.length)     var j = 0     for(i in 1 until pattern.length){      \/\/\u4e0b\u9762\u8fd9\u4e2a\u5faa\u73af\u600e\u4e48\u7406\u89e3?         while(j > 0 && pattern[j] != pattern[i])             j = pmt[j - 1]                 pmt[i] = if(pattern[j] == pattern[i]) ++j else j     }     return pmt } <\/code><\/pre>\n
\u5728 SO( https:\/\/stackoverflow.com\/questions\/38757553) \u4e0a\u6709\u4e00\u4e2a\u89e3\u91ca:<\/p>\n
“if b[i] = j, then for any k < j, s.t P[0..k-1] == P[i-k..i-1], we know that b[j] >= k. At the same time, obviously b[i] > b[j] or b[i] = 0.<\/p>\n
What this means is that we can easily enumerate the k values from largest to smallest, by going through b[i] -> b[b[i]] -> b[b[b[i]]]… and so on. “<\/p>\n
\u8bf4\u5b9e\u8bdd\u6ca1\u6709\u592a\u770b\u61c2. \u90e8\u5206\u5339\u914d\u8868 \/next \u8868 \/SO \u4e0a\u9762\u7684 b\uff0c\u90fd\u662f\u4e00\u4e2a\u4e1c\u897f<\/p>\n<\/p><\/div>\n
 \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (1<\/span>)        <\/div>\n
 <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
    \n
  • \n
    \n
    \n
     \u8cc7\u6df1\u5927\u4f6c : QingchuanZhang <\/span>  <\/div>\n
     <\/i>            <\/span> <\/div>\n<\/p><\/div>\n
                                                                 \u5b89\u5229\u4e00\u4e0b\uff1a[\u6211\u7684 kmp \u6559\u7a0b]( https:\/\/github.com\/SamZhangQingChuan\/Editorials\/blob\/master\/%E6%95%99%E7%A8%8B\/%E5%AD%97%E7%AC%A6%E4%B8%B2\/KMP\/KMP.pdf)                                                            <\/div>\n<\/p><\/div>\n<\/li>\n
  • \n","protected":false},"excerpt":{"rendered":"
    KMP \u91cc\u9762\u7684\u90e8\u5206\u5339\u914d\u8868\u6784\u9020\u54ea\u4f4d\u80fd…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/86345"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=86345"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/86345\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=86345"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=86345"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=86345"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}