{"id":243,"date":"2026-07-31T16:07:09","date_gmt":"2026-07-31T08:07:09","guid":{"rendered":"https:\/\/huxiaole.cloud\/?p=243"},"modified":"2026-07-31T16:07:15","modified_gmt":"2026-07-31T08:07:15","slug":"p5410-%e3%80%90%e6%a8%a1%e6%9d%bf%e3%80%91%e6%89%a9%e5%b1%95-kmp-exkmp%ef%bc%88z-%e5%87%bd%e6%95%b0%ef%bc%89","status":"publish","type":"post","link":"https:\/\/huxiaole.cloud\/index.php\/2026\/07\/31\/p5410-%e3%80%90%e6%a8%a1%e6%9d%bf%e3%80%91%e6%89%a9%e5%b1%95-kmp-exkmp%ef%bc%88z-%e5%87%bd%e6%95%b0%ef%bc%89\/","title":{"rendered":"P5410 \u3010\u6a21\u677f\u3011\u6269\u5c55 KMP \/ exKMP\uff08Z \u51fd\u6570\uff09"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">P5410 \u3010\u6a21\u677f\u3011\u6269\u5c55 KMP \/ exKMP\uff08Z \u51fd\u6570\uff09<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32 $a,b$\uff0c\u4f60\u8981\u6c42\u51fa\u4e24\u4e2a\u6570\u7ec4\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$b$ \u7684 $z$ \u51fd\u6570\u6570\u7ec4 $z$\uff0c\u5373 $b$ \u4e0e $b$ \u7684\u6bcf\u4e00\u4e2a\u540e\u7f00\u7684 LCP \u957f\u5ea6\u3002<\/li>\n\n\n\n<li>$b$ \u4e0e $a$ \u7684\u6bcf\u4e00\u4e2a\u540e\u7f00\u7684 LCP \u957f\u5ea6\u6570\u7ec4 $p$\u3002<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u4e8e\u4e00\u4e2a\u957f\u5ea6\u4e3a $n$ \u7684\u6570\u7ec4 $a$\uff0c\u8bbe\u5176\u6743\u503c\u4e3a $\\operatorname{xor}_{i=1}^n i \\times (a_i + 1)$\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e24\u884c\u4e24\u4e2a\u5b57\u7b26\u4e32 $a,b$\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u7b2c\u4e00\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a $z$ \u7684\u6743\u503c\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u7b2c\u4e8c\u884c\u4e00\u4e2a\u6574\u6570\uff0c\u8868\u793a $p$ \u7684\u6743\u503c\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #1<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>aaaabaa\naaaaa<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>6\n21<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8bf4\u660e\/\u63d0\u793a<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6837\u4f8b\u89e3\u91ca\uff1a<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">$z = {5\\ 4\\ 3\\ 2\\ 1}$\uff0c$p = {4\\ 3\\ 2\\ 1\\ 0\\ 2\\ 1}$\u3002<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u6570\u636e\u8303\u56f4\uff1a<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u4e8e\u7b2c\u4e00\u4e2a\u6d4b\u8bd5\u70b9\uff0c$|a|,|b| \\le 2 \\times 10^3$\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u4e8e\u7b2c\u4e8c\u4e2a\u6d4b\u8bd5\u70b9\uff0c$|a|,|b| \\le 2 \\times 10^5$\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5bf9\u4e8e $100\\%$ \u7684\u6570\u636e\uff0c$1 \\le |a|,|b| \\le 2 \\times 10^7$\uff0c\u6240\u6709\u5b57\u7b26\u5747\u4e3a\u5c0f\u5199\u5b57\u6bcd\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u601d\u8def<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Z \u51fd\u6570\u7528\u4e8e\u6c42\u539f\u5b57\u7b26\u4e32\u4e0e\u6bcf\u4e2a\u540e\u7f00\u7684\u6700\u5927\u5339\u914d\u957f\u5ea6\u3002$z[1]=n$\u3002\u904d\u5386\u4f4d\u7f6e i \u65f6\uff0c\u5982\u679c i \u4f4d\u4e8e\u4e4b\u524d\u7684\u5339\u914d\u76d2\u5b50 $[l,r]$ \u5185\uff0c\u5c31\u4ece\u5bf9\u5e94\u4f4d\u7f6e $z[i\u2212l+1]$ \u7ee7\u627f\uff0c\u4f46\u6700\u591a\u7ee7\u627f $r\u2212i+1$ \u4e2a\u5b57\u7b26\uff1b\u7136\u540e\u7ee7\u7eed\u66b4\u529b\u6269\u5c55\uff0c\u5e76\u66f4\u65b0\u6700\u9760\u53f3\u7684\u5339\u914d\u76d2\u5b50\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">GPT Said<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">z\u51fd\u6570\u7528\u4e8e\u6c42\u89e3\u539f\u5b57\u7b26\u4e32\u548c\u5b83\u7684\u6bcf\u4e2a\u540e\u7f00\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u957f\u5ea6\u3002<br>$z[1]$\u662f\u5b8c\u5168\u5339\u914d\u7684\uff0c\u6240\u4ee5\u9ed8\u8ba4\u5c31\u662f\u5b57\u7b26\u4e32\u957f\u5ea6\u3002<br>\u7136\u540e\u5f00\u59cb\u904d\u5386\uff0c\u8ba1\u7b97\u8fc7\u7a0b\u4e2d\u7ef4\u62a4$[l,r]$\uff0c\u6ee1\u8db3$s[l\u2026r]$\u4e0e\u5b57\u7b26\u4e32\u524d\u7f00\u76f8\u540c\u3002\u904d\u5386\u5230\u4f4d\u7f6ei\u65f6\uff0c\u5982\u679c$i&lt;=r$\uff0c\u8bf4\u660e$i$\u5728\u5df2\u77e5\u5339\u914d\u533a\u95f4\u5185\uff0c\u53ef\u4ee5\u5148\u4ee4 $z[i]=min(z[i-l+1],r-i+1)$ \u7ee7\u627f\u5df2\u7ecf\u786e\u5b9a\u7684\u5339\u914d\u957f\u5ea6\uff1b\u5982\u679c$i&gt;r$\uff0c\u5219$z[i]=0$\u5f00\u59cb\u3002\u968f\u540e\u7ee7\u7eed\u9010\u5b57\u7b26\u66b4\u529b\u6bd4\u8f83\uff0c\u6269\u5c55$z[i]$\u3002\u5982\u679c\u5f53\u524d\u5339\u914d\u533a\u95f4$[i,i+z[i]-1]$\u7684\u53f3\u7aef\u70b9\u8d85\u8fc7\u4e86$r$\uff0c\u5c31\u66f4\u65b0<br>$l=i$ , $r=i+z[i]-1$<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>for (int i = 2; i &lt;= n; i++) {\n    \/\/ 1. \u7ee7\u627f\n    if (i &lt;= r) {\n        z&#91;i] = min(z&#91;i - l + 1], r - i + 1);\n    }\n\n    \/\/ 2. \u66b4\u529b\u6269\u5c55\n    while (i + z&#91;i] &lt;= n &amp;&amp;\n           s&#91;i + z&#91;i]] == s&#91;1 + z&#91;i]]) {\n        z&#91;i]++;\n    }\n\n    \/\/ 3. \u66f4\u65b0\u76d2\u5b50\n    if (i + z&#91;i] - 1 &gt; r) {\n        l = i;\n        r = i + z&#91;i] - 1;\n    }\n}<\/code><\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">\u6700\u7b80\u8bb0\u5fc6\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>i \u5728\u76d2\u5b50\u5185 \u2192 \u5148\u7ee7\u627f\n\u7ee7\u627f\u4e0d\u80fd\u8d8a\u8fc7 r \u2192 \u53d6 min\n\u7136\u540e\u7ee7\u7eed\u6bd4\u8f83 \u2192 \u66b4\u529b\u6269\u5c55\n\u6269\u5c55\u5f97\u66f4\u8fdc \u2192 \u66f4\u65b0 &#91;l,r]<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/Sunshine sunshine ladybugs awake,\n\/\/Clap your hooves and do a little shack.\n#include&lt;bits\/stdc++.h&gt;\n#define int long long\n#define endl \"\\n\"\n\nusing namespace std;\n\nusing PII=pair&lt;int,int&gt; ;\nconst int MAXN=300005;\nconst int mod=998244353;\nconst int INF=0x3f3f3f3f3f3f3f3f;\n\nvoid solve(){\n    string a,b;\n    cin&gt;&gt;a&gt;&gt;b;\n\n    a=\" \"+a;\n    b=\" \"+b;\n\n    int n=(int)a.size()-1;\n    int m=(int)b.size()-1;\n\n    vector&lt;int&gt; z(m+1);\n    z&#91;1]=m;\n\n    int l=1,r=0;\n\n    for(int i=2;i&lt;=m;i++){\n        if(i&lt;=r){\n            int k=i-l+1;\n            int remain=r-i+1;\n\n            z&#91;i]=min(z&#91;k],remain);\n        }\n\n        while(i+z&#91;i]&lt;=m&amp;&amp;\n              b&#91;1+z&#91;i]]==b&#91;i+z&#91;i]]){\n            z&#91;i]++;\n        }\n\n        if(z&#91;i]&gt;0&amp;&amp;i+z&#91;i]-1&gt;r){\n            l=i;\n            r=i+z&#91;i]-1;\n        }\n    }\n\n    int answerZ=0;\n    for(int i=1;i&lt;=m;i++){\n        answerZ^=1ll*i*(z&#91;i]+1);\n    }\n\n\n\n    int answerP=0;\n    l=1;r=0;\n    for(int i=1;i&lt;=n;i++){\n        int now=0;\n        if(i&lt;=r){\n            int k=i-l+1;\n            int remain=r-i+1;\n            now=min(z&#91;k],remain);\n        }\n\n        while(now&lt;m&amp;&amp;\n              i+now&lt;=n&amp;&amp;\n              a&#91;i+now]==b&#91;1+now]){\n            now++;\n        }\n\n        if(now&gt;0&amp;&amp;i+now-1&gt;r){\n            l=i;\n            r=i+now-1;\n        }\n\n        answerP^=1ll*i*(now+1);\n    }\n\n    cout&lt;&lt;answerZ&lt;&lt;endl;\n    cout&lt;&lt;answerP&lt;&lt;endl;\n}\n\nsigned main() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    \/\/int t;cin&gt;&gt;t;while(t--)\n    solve();\n    return 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>P5410 \u3010\u6a21\u677f\u3011\u6269\u5c55 KMP \/ exKMP\uff08Z \u51fd\u6570\uff09 \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32 $a,b$\uff0c\u4f60\u8981\u6c42\u51fa\u4e24 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":101,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[11,18],"tags":[],"class_list":["post-243","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-11","category-luogu"],"_links":{"self":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/243","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/comments?post=243"}],"version-history":[{"count":1,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/243\/revisions"}],"predecessor-version":[{"id":244,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/243\/revisions\/244"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media\/101"}],"wp:attachment":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media?parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/categories?post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/tags?post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}