{"id":260,"date":"2024-03-27T08:44:11","date_gmt":"2024-03-27T00:44:11","guid":{"rendered":"https:\/\/www.nenuacm.top\/?p=260"},"modified":"2024-03-27T09:25:11","modified_gmt":"2024-03-27T01:25:11","slug":"pta%e5%a4%a9%e6%a2%af%e8%b5%9bl3-029-%e8%bf%98%e5%8e%9f%e6%96%87%e4%bb%b6","status":"publish","type":"post","link":"https:\/\/www.nenuacm.top\/index.php\/2024\/03\/27\/pta%e5%a4%a9%e6%a2%af%e8%b5%9bl3-029-%e8%bf%98%e5%8e%9f%e6%96%87%e4%bb%b6\/","title":{"rendered":"PTA\u5929\u68af\u8d5bL3-029 \u8fd8\u539f\u6587\u4ef6"},"content":{"rendered":"\n

\u4e00\u4efd\u91cd\u8981\u6587\u4ef6\u88ab\u6495\u6210\u4e24\u534a\uff0c\u5176\u4e2d\u4e00\u534a\u8fd8\u88ab\u9001\u8fdb\u4e86\u788e\u7eb8\u673a\u3002\u6211\u4eec\u5c06\u788e\u7eb8\u673a\u91cc\u627e\u5230\u7684\u7eb8\u6761\u8fdb\u884c\u7f16\u53f7\uff0c\u5982\u56fe 1 \u6240\u793a\u3002\u7136\u540e\u6839\u636e\u65ad\u53e3\u7684\u6298\u7ebf\u5f62\u72b6\u8ddf\u6ca1\u6709\u5207\u788e\u7684\u534a\u5f20\u7eb8\u8fdb\u884c\u5339\u914d\uff0c\u6700\u540e\u8fd8\u539f\u6210\u56fe 2 \u7684\u6837\u5b50\u3002\u8981\u6c42\u4f60\u8f93\u51fa\u8fd8\u539f\u540e\u7eb8\u6761\u7684\u6b63\u786e\u62fc\u63a5\u987a\u5e8f\u3002<\/p>\n\n\n\n

\"file1.JPG\"\/<\/div><\/figure>\n\n\n\n

\u56fe1 \u7eb8\u6761\u7f16\u53f7<\/p>\n\n\n\n

\"file2.JPG\"\/<\/div><\/figure>\n\n\n\n

\u56fe2 \u8fd8\u539f\u7ed3\u679c<\/p>\n\n\n\n

\u8f93\u5165\u683c\u5f0f\uff1a<\/h3>\n\n\n\n

\u8f93\u5165\u9996\u5148\u5728\u7b2c\u4e00\u884c\u4e2d\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570 N<\/em>\uff081<N<\/em>\u2264105\uff09\uff0c\u4e3a\u6ca1\u6709\u5207\u788e\u7684\u534a\u5f20\u7eb8\u4e0a\u65ad\u53e3\u6298\u7ebf\u89d2\u70b9\u7684\u4e2a\u6570\uff1b\u968f\u540e\u4e00\u884c\u7ed9\u51fa\u4ece\u5de6\u5230\u53f3 N<\/em> \u4e2a\u6298\u7ebf\u89d2\u70b9\u7684\u9ad8\u5ea6\u503c\uff08\u5747\u4e3a\u4e0d\u8d85\u8fc7 100 \u7684\u975e\u8d1f\u6574\u6570\uff09\u3002<\/p>\n\n\n\n

\u968f\u540e\u4e00\u884c\u7ed9\u51fa\u4e00\u4e2a\u6b63\u6574\u6570 M<\/em>\uff08\u2264100\uff09\uff0c\u4e3a\u788e\u7eb8\u673a\u91cc\u7684\u7eb8\u6761\u6570\u91cf\u3002\u63a5\u4e0b\u53bb\u6709 M<\/em> \u884c\uff0c\u5176\u4e2d\u7b2c i<\/em> \u884c\u7ed9\u51fa\u7f16\u53f7\u4e3a i<\/em>\uff081\u2264i<\/em>\u2264M<\/em>\uff09\u7684\u7eb8\u6761\u7684\u65ad\u53e3\u4fe1\u606f\uff0c\u683c\u5f0f\u4e3a\uff1a<\/p>\n\n\n\n

K h[1] h[2] ... h[K]<\/code><\/pre>\n\n\n\n
\u5176\u4e2d K<\/code> \u662f\u65ad\u53e3\u6298\u7ebf\u89d2\u70b9\u7684\u4e2a\u6570\uff08\u4e0d\u8d85\u8fc7 104+1\uff09\uff0c\u540e\u9762\u662f\u4ece\u5de6\u5230\u53f3 K<\/code> \u4e2a\u6298\u7ebf\u89d2\u70b9\u7684\u9ad8\u5ea6\u503c\u3002\u4e3a\u7b80\u5355\u8d77\u89c1\uff0c\u8fd9\u4e2a\u201c\u9ad8\u5ea6\u201d\u8ddf\u6ca1\u6709\u5207\u788e\u7684\u534a\u5f20\u7eb8\u4e0a\u65ad\u53e3\u6298\u7ebf\u89d2\u70b9\u7684\u9ad8\u5ea6\u662f\u4e00\u81f4\u7684\u3002<\/p>\n\n\n\n
\u8f93\u51fa\u683c\u5f0f\uff1a<\/h3>\n\n\n\n
\u5728\u4e00\u884c\u4e2d\u8f93\u51fa\u8fd8\u539f\u540e\u7eb8\u6761\u7684\u6b63\u786e\u62fc\u63a5\u987a\u5e8f\u3002\u7eb8\u6761\u7f16\u53f7\u95f4\u4ee5\u4e00\u4e2a\u7a7a\u683c\u5206\u9694\uff0c\u884c\u9996\u5c3e\u4e0d\u5f97\u6709\u591a\u4f59\u7a7a\u683c\u3002<\/p>\n\n\n\n
\u9898\u76ee\u6570\u636e\u4fdd\u8bc1\u5b58\u5728\u552f\u4e00\u89e3\u3002<\/p>\n\n\n\n
\u8f93\u5165\u6837\u4f8b\uff1a<\/h3>\n\n\n\n
17\n95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80\n6\n4 68 58 58 80\n3 81 68 68\n3 95 70 80\n3 68 60 80\n5 80 72 88 81 81\n4 80 97 97 68<\/code><\/pre>\n\n\n\n
\u8f93\u51fa\u6837\u4f8b\uff1a<\/h3>\n\n\n\n
3 6 1 5 2 4<\/code><\/pre>\n\n\n\n
\u9898\u89e3<\/h3>\n\n\n\n
\u6ce8\u610f\u5230\u6574\u4e2a\u62fc\u63a5\u8fc7\u7a0b\u7c7b\u4f3c\u4e8e\u6a21\u5f0f\u5339\u914d\uff0c\u7528 68 58 58 80 \u4e3e\u4f8b\uff0c\u8fd9\u4e00\u5e8f\u5217\u5728\u539f\u5e8f\u5217\u7684\u7b2c\u516d\u4e2a\u4f4d\u7f6e\u5339\u914d\u4e0a\u4e86\u3002\u7531\u4e8e\u6298\u7eb8\u7684\u9ad8\u5ea6\u4e3a\u4e0d\u8d85\u8fc7100\u7684\u975e\u8d1f\u6574\u6570\uff0c\u6240\u4ee5\u53ef\u4ee5\u7528\u5b57\u7b26\u7c7b\u578b\u53bb\u5b58\u50a8\u6bcf\u4e00\u4e2a\u6570\u5b57\uff0c\u535a\u4e3b\u662f\u7528string\u53bb\u5b58\u50a8\u7684\uff0c\u6548\u679c\u662f\u4e00\u6837\u7684\u3002\u603b\u5171\u6709$m = 100$\u4e2a\u6a21\u5f0f\u4e32\uff0c\u7531$N$\u662f$1e^{5}$\uff0c\u5355\u4e2a\u6a21\u5f0f\u4e32\u7684\u957f\u5ea6\u6700\u957f$k = 1e^{4}$\uff0c\u5982\u679c\u66b4\u529b\u5339\u914d\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a$O(m * n * k)$\u4e00\u773c\u8fc7\u4e0d\u4e86\uff0c\u6240\u4ee5\u6211\u4eec\u9700\u8981\u7528$kmp$\u8fdb\u884c\u4f18\u5316\uff0c\u5c06\u5355\u6b21\u6a21\u5f0f\u5339\u914d\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4f18\u5316\u4e3a$O(n + k)$\uff0c\u90a3\u4e48\u603b\u590d\u6742\u5ea6\u4e3a$O(m * (n + k))$\u8db3\u591f\u901a\u8fc7\u672c\u9898\u3002
\u9700\u8981\u6ce8\u610f\u4e00\u70b9\u7684\u662f\uff0c\u6240\u6709\u6a21\u5f0f\u4e32\u4e2d\u53ef\u80fd\u5b58\u5728\u4e00\u4e2a\u6a21\u5f0f\u4e32\u662f\u53e6\u4e00\u4e2a\u6a21\u5f0f\u4e32\u524d\u7f00\u7684\u53ef\u80fd\uff0c\u5c31\u4f1a\u9020\u6210\u4e24\u4e2a\u6a21\u5f0f\u4e32\u5339\u914d\u5230\u4e86\u540c\u4e00\u4e2a\u4f4d\u7f6e\u3002\u4f8b\u5982$s = “abcab”$\uff0c$p1 = “ab”$\uff0c$p2 = “abc”$\uff0c\u90fd\u5728\u7b2c\u4e00\u4e2a\u4f4d\u7f6e\u6210\u529f\u5339\u914d\u3002\u7136\u540e\u6211\u4eec\u6709\u5982\u4e0b\u8003\u8651\uff0c\u9898\u76ee\u4fdd\u8bc1\u7ed3\u679c\u552f\u4e00\uff0c\u90a3\u4e48\u4e00\u4e2a\u6a21\u5f0f\u4e32\u5fc5\u7136\u80fd\u552f\u4e00\u5339\u914d\u5230\u539f\u4e32\u4e2d\u7684\u4e00\u4e2a\u4f4d\u7f6e\uff0c\u9020\u6210\u5339\u914d\u7ed3\u679c\u4e0d\u552f\u4e00\u7684\u539f\u56e0\u662f\u5176\u4e2d\u4e00\u4e2a\u6a21\u5f0f\u4e32\u662f\u53e6\u4e00\u4e2a\u6a21\u5f0f\u4e32\u7684\u524d\u7f00\uff0c\u5982\u679c\u6211\u4eec\u6309\u7167\u6a21\u5f0f\u4e32\u957f\u5ea6\u4ece\u5927\u5230\u5c0f\u7684\u987a\u5e8f\u5339\u914d\uff0c\u5e76\u4e14\u5c06\u5339\u914d\u7ed3\u679c\u8bb0\u5f55\uff0c\u5982\u679c\u53e6\u4e00\u4e2a\u4e32\u5339\u914d\u5230\u540c\u4e00\u4f4d\u7f6e\u5c31\u7ee7\u7eed\u5339\u914d\uff0c\u76f4\u5230\u5339\u914d\u5230\u4e00\u4e2a\u672a\u88ab\u5339\u914d\u7684\u4f4d\u7f6e\u3002<\/p>\n\n\n\n
\u53c2\u8003\u4ee3\u7801<\/p>\n\n\n\n
#include<iostream>\n#include<algorithm>\n#include<cmath>\n#include<vector>\n#include<map>\n#include<bitset>\n#include<string>\n#include<cstring>\n\nusing namespace std;\n\nbool vis[100005];\n\nstruct node{\n\tint id, pos, len;\n\tvector<string> s;\n};\n\nvoid getNext(vector<string> &s, vector<int> &nex){\n\tint n = nex.size() - 1;\n\tint i = 1, j = 0;\n\tnex[1] = 0;\n\twhile(i < n){\n\t\tif(s[i] == s[j] || j == 0){\n\t\t\ti++,j++;\n\t\t\tnex[i] = j;\n\t\t}else j = nex[j];\n\t}\n}\n\nint kmp(vector<string> &s, vector<string> &p, vector<int> &nex){\n\tint n = s.size() - 1;\n\tint len = p.size() - 1;\n\tint i = 1, j = 1;\n\tint pos = -1;\n\twhile(i <= n){\n\t\tif(j == len + 1){\n\t\t\tif(vis[i - len] == 0){\n\t\t\t\tpos = i - len;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tj = 1;\n\t\t}\n\t\tif(s[i] == p[j] || j == 0){\n\t\t\ti++, j++;\n\t\t}else j = nex[j];\n\t}\n\tif(j == len + 1) pos = i - len;\n\treturn pos;\n}\n\nvoid solve() {\n\tint n;\n\tcin >> n;\n\tvector<string> a(n + 1);\n\tfor(int i = 1; i <= n; i++) cin >> a[i];\n\tint q;\n\tcin >> q;\n\tvector<node> ans(q + 1);\n\tfor(int i = 1, x; i <= q; i++){\n\t\tcin >> x;\n\t\tans[i].s = vector<string>(x + 1);\n\t\tans[i].id = i;\n\t\tans[i].len = x;\n\t\tfor(int j = 1; j <= x; j++) cin >> ans[i].s[j];\n\t}\t\n\tsort(ans.begin() + 1, ans.end(), [](node a, node b){\n\t\treturn a.len < b.len;\n\t});\n\tfor(int i = 1; i <= q; i++){\n\t\tvector<int> nex(ans[i].len + 1);\n\t\tgetNext(ans[i].s, nex);\n\t\tans[i].pos = kmp(a, ans[i].s, nex);\n\t\tvis[ans[i].pos] = 1;\n\t}\n\tsort(ans.begin() + 1, ans.end(),[](node a, node b){\n\t\treturn a.pos < b.pos;\t\n\t});\n\tfor(int i = 1; i <= q; i++) cout << ans[i].id << \" \\n\"[i == q];\n}\n\nint main() {\n    int t = 1;\n\/\/    cin >> t;\n    while (t--)\n        solve();\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u4efd\u91cd\u8981\u6587\u4ef6\u88ab\u6495\u6210\u4e24\u534a\uff0c\u5176\u4e2d\u4e00\u534a\u8fd8\u88ab\u9001\u8fdb\u4e86\u788e\u7eb8\u673a\u3002\u6211\u4eec\u5c06\u788e\u7eb8\u673a\u91cc\u627e\u5230\u7684\u7eb8\u6761\u8fdb\u884c\u7f16\u53f7\uff0c\u5982\u56fe 1 \u6240\u793a\u3002\u7136\u540e\u6839\u636e\u65ad […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-260","post","type-post","status-publish","format-standard","hentry","category-10"],"_links":{"self":[{"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/posts\/260","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/comments?post=260"}],"version-history":[{"count":4,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/posts\/260\/revisions"}],"predecessor-version":[{"id":272,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/posts\/260\/revisions\/272"}],"wp:attachment":[{"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/media?parent=260"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/categories?post=260"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.nenuacm.top\/index.php\/wp-json\/wp\/v2\/tags?post=260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}