{"id":95,"date":"2023-03-27T21:44:00","date_gmt":"2023-03-27T13:44:00","guid":{"rendered":"https:\/\/solost.cn\/?p=95"},"modified":"2023-04-24T20:30:48","modified_gmt":"2023-04-24T12:30:48","slug":"188","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=95","title":{"rendered":"KMP"},"content":{"rendered":"<h3>\u53c2\u8003\u6587\u7ae0<\/h3>\n<p><a href=\"https:\/\/www.acwing.com\/file_system\/file\/content\/whole\/index\/content\/6255932\/\">\u6587\u7ae0\u94fe\u63a5<\/a><\/p>\n<h2>\u6a21\u677f\u4ee3\u7801<\/h2>\n<pre><code class=\"lang-cpp\">\/\/ s[]\u662f\u957f\u6587\u672c\uff0cp[]\u662f\u6a21\u5f0f\u4e32\uff0cn\u662fs\u7684\u957f\u5ea6\uff0cm\u662fp\u7684\u957f\u5ea6\n\u6c42\u6a21\u5f0f\u4e32\u7684Next\u6570\u7ec4\uff1a\nfor (int i = 2, j = 0; i &lt;= m; i ++ )\n{\n    while (j &amp;&amp; p[i] != p[j + 1]) j = ne[j];\n    if (p[i] == p[j + 1]) j ++ ;\n    ne[i] = j;\n}\n\n\/\/ \u5339\u914d\nfor (int i = 1, j = 0; i &lt;= n; i ++ )\n{\n    while (j &amp;&amp; s[i] != p[j + 1]) j = ne[j];\n    if (s[i] == p[j + 1]) j ++ ;\n    if (j == m)\n    {\n        j = ne[j];\n        \/\/ \u5339\u914d\u6210\u529f\u540e\u7684\u903b\u8f91\n    }\n}<\/code><\/pre>\n<h2>\u4f8b\u9898<\/h2>\n<pre><code class=\"lang-cpp\">#include &lt;iostream&gt;\n\nusing namespace std;\n\nconst int N = 1000010;\nchar p[N], s[N]; \/\/ \u7528 p \u6765\u5339\u914d s\n\/\/ \u201cnext\u201d \u6570\u7ec4\uff0c\u82e5\u7b2c i \u4f4d\u5b58\u50a8\u503c\u4e3a k\n\/\/ \u8bf4\u660e p[0...i] \u5185\u6700\u957f\u76f8\u7b49\u524d\u540e\u7f00\u7684\u524d\u7f00\u7684\u6700\u540e\u4e00\u4f4d\u4e0b\u6807\u4e3a k\n\/\/ \u5373 p[0...k] == p[i-k...i]\nint ne[N]; \nint n, m; \/\/ n \u662f\u6a21\u677f\u4e32\u957f\u5ea6 m \u662f\u6a21\u5f0f\u4e32\u957f\u5ea6\n\nint main()\n{\n    cin &gt;&gt; n &gt;&gt; p &gt;&gt; m &gt;&gt; s;\n\n    \/\/ p[0...0] \u7684\u533a\u95f4\u5185\u4e00\u5b9a\u6ca1\u6709\u76f8\u7b49\u524d\u540e\u7f00\n    ne[0] = -1;\n\n    \/\/ \u6784\u9020\u6a21\u677f\u4e32\u7684 next \u6570\u7ec4\n    for (int i = 1, j = -1; i &lt; n; i ++)\n    {\n        while (j != -1 &amp;&amp; p[i] != p[j + 1])\n        {\n            \/\/ \u82e5\u524d\u540e\u7f00\u5339\u914d\u4e0d\u6210\u529f\n            \/\/ \u53cd\u590d\u4ee4 j \u56de\u9000\uff0c\u76f4\u81f3\u5230 -1 \u6216\u662f s[i] == s[j + 1]\n            j = ne[j];\n        }\n        if (p[i] == p[j + 1]) \n        {\n            j ++; \/\/ \u5339\u914d\u6210\u529f\u65f6\uff0c\u6700\u957f\u76f8\u7b49\u524d\u540e\u7f00\u53d8\u957f\uff0c\u6700\u957f\u76f8\u7b49\u524d\u540e\u7f00\u6700\u540e\u4e00\u4f4d\u53d8\u5927\n        }\n        ne[i] = j; \/\/ \u4ee4 ne[i] = j\uff0c\u4ee5\u65b9\u4fbf\u8ba1\u7b97 next[i + 1]\n    }\n\n    \/\/ kmp start !\n    for (int i = 0, j = -1; i &lt; m; i ++)\n    {\n       while (j != -1 &amp;&amp; s[i] != p[j + 1])\n       {\n           j = ne[j];\n       }\n       if (s[i] == p[j + 1])\n       {\n           j ++; \/\/ \u5339\u914d\u6210\u529f\u65f6\uff0c\u6a21\u677f\u4e32\u6307\u5411\u4e0b\u4e00\u4f4d\n       }\n       if (j == n - 1) \/\/ \u6a21\u677f\u4e32\u5339\u914d\u5b8c\u6210\uff0c\u7b2c\u4e00\u4e2a\u5339\u914d\u5b57\u7b26\u4e0b\u6807\u4e3a 0\uff0c\u6545\u5230 n - 1\n       {\n           \/\/ \u5339\u914d\u6210\u529f\u65f6\uff0c\u6587\u672c\u4e32\u7ed3\u675f\u4f4d\u7f6e\u51cf\u53bb\u6a21\u5f0f\u4e32\u957f\u5ea6\u5373\u4e3a\u8d77\u59cb\u4f4d\u7f6e\n           cout &lt;&lt; i - j &lt;&lt; &#039; &#039;;\n\n           \/\/ \u6a21\u677f\u4e32\u5728\u6a21\u5f0f\u4e32\u4e2d\u51fa\u73b0\u7684\u4f4d\u7f6e\u53ef\u80fd\u662f\u91cd\u53e0\u7684\n           \/\/ \u9700\u8981\u8ba9 j \u56de\u9000\u5230\u4e00\u5b9a\u4f4d\u7f6e\uff0c\u518d\u8ba9 i \u52a0 1 \u7ee7\u7eed\u8fdb\u884c\u6bd4\u8f83\n           \/\/ \u56de\u9000\u5230 ne[j] \u53ef\u4ee5\u4fdd\u8bc1 j \u6700\u5927\uff0c\u5373\u5df2\u7ecf\u6210\u529f\u5339\u914d\u7684\u90e8\u5206\u6700\u957f\n           j = ne[j]; \n       }\n    }\n\n   return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u53c2\u8003\u6587\u7ae0 \u6587\u7ae0\u94fe\u63a5 \u6a21\u677f\u4ee3\u7801 \/\/ s[]\u662f\u957f\u6587\u672c\uff0cp[]\u662f\u6a21\u5f0f\u4e32\uff0cn\u662fs\u7684\u957f\u5ea6\uff0cm\u662fp\u7684\u957f\u5ea6 \u6c42\u6a21\u5f0f\u4e32\u7684Next\u6570\u7ec4\uff1a for (int i = 2, j = 0; i &lt;= m; i ++ ) { while (j &amp;&amp; p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j ++ ; ne[i] = j; } \/\/ \u5339\u914d for (int i = 1, j = 0; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72],"tags":[41],"class_list":["post-95","post","type-post","status-publish","format-standard","hentry","category-acm","tag-kmp"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/95","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=95"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/95\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=95"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=95"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=95"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}