![\"\"](\"https:\/\/forelink.top\/wp-content\/uploads\/2023\/05\/image-51-1024x678.png\")
<\/div><\/figure>\n\n\n\n\u7528\u5230\u7c7b\u4f3c\u5feb\u901f\u6392\u5e8f\u7684\u5206\u6cbb\u6cd5\u3002\u5feb\u901f\u6392\u5e8f\u7684\u601d\u60f3\u662f\u628a\u6570\u591a\u6b21\u5206\u4e3a\u4e09\u4e2a\u533a\u95f4\uff08\u5c0f\u4e8e\u57fa\u51c6\u6570 \/ \u7b49\u4e8e\u57fa\u51c6\u6570 \/ \u5927\u4e8e\u57fa\u51c6\u6570\uff09\uff0c\u518d\u5c06\u5404\u4e2a\u6392\u5e8f\u597d\u7684\u5404\u4e2a\u533a\u95f4\u62fc\u5728\u4e00\u8d77\uff0c\u5c31\u80fd\u5f97\u5230\u4e00\u4e2a\u6392\u5e8f\u597d\u7684\u5b8c\u6574\u6570\u7ec4\u3002<\/strong><\/p>\n\n\n\n \u56e0\u4e3a\u5206\u4e3a\u4e09\u4e2a\u533a\u95f4\u540e\uff0c\u603b\u6570\u4e0d\u53d8\uff0c\u6240\u4ee5\u76f4\u63a5\u5bf9\u539f\u6570\u7ec4\u8fdb\u884c\u8986\u5199\u5373\u53ef\u3002<\/strong><\/p>\n\n\n\n \u5feb\u901f\u6392\u5e8f\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n \u90a3\u4e48\u8981\u6c42\u65e0\u5e8f\u6570\u7ec4\u7b2ck\u5c0f\u7684\u6570\uff0c\u4f1a\u60f3\u5230\u8fdb\u884c\u6392\u5e8f\u540e\u76f4\u63a5\u8f93\u51fa\u5bf9\u5e94\u4e0b\u6807\u7684\u90a3\u4e2a\u6570\u3002\u7136\u800c\u76f4\u63a5\u6392\u5e8f\u590d\u6742\u5ea6\u662fO\uff08nlogn\uff09\uff0c\u5927\u6982\u662f10^8\u8fd9\u4e2a\u7ea7\u522b\uff0c\u6392\u5e8f\u540e\u4ea4\u4e5f\u662f\u53ea\u670960\u5206\uff0c\u8fc7\u4e0d\u4e86\u3002<\/strong><\/p>\n\n\n\n \u81ea\u7136\u60f3\u5230\u7528\u4e8c\u5206\u7684\u601d\u60f3\u53bb\u627e \u7b2ck\u5c0f\u7684\u6570\u3002\u5feb\u901f\u6392\u5e8f\u662f\u4ee5\u57fa\u51c6\u6570\u628a\u6570\u7ec4\u5206\u4e3a\u4e24\u4e2a\u90e8\u5206L \u548c R\uff0c\u5982\u679c\u8981\u627e\u7b2ck\u5c0f\u7684\u6570\uff0c\u82e5L\u7684\u53f3\u8fb9\u754c\u7684\u6570Lr\u6bd4k\u5927\uff0c\u90a3\u7b2ck\u5c0f\u7684\u6570\u5c31\u5728L\u4e2d\uff0c\u8c03\u7528\u51fd\u6570\u7ee7\u7eed\u5bf9L\u5212\u5206\u5373\u53ef\u3002\u627e\u5230\u7b54\u6848\u7684\u65f6\u5019\u662fk\u7b49\u4e8e\u57fa\u51c6\u6570\u7684\u65f6\u5019\uff08\u57fa\u51c6\u6570\u662f\u5728\u533a\u95f4\u91cc\u53d6\u7684\uff0c\u4e0d\u4f1a\u51fa\u73b0\u6ca1\u6709\u5bf9\u5e94\u7684\u60c5\u51b5\uff09<\/strong><\/p>\n\n\n\n \u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n \u9898\u76ee\uff1a<\/strong><\/p>\n\n\n\n \u6837\u4f8b\uff1a<\/strong><\/p>\n\n\n\n \u4e00\u9053\u641c\u7d22\u9898\u3002<\/strong><\/p>\n\n\n\n \u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n \u9898\u76ee\uff1a<\/strong><\/p>\n\n\n\n \u6837\u4f8b\uff1a<\/strong><\/p>\n\n\n\n \u82e5\u6587\u672c\u4e32\u957f\u5ea6\u4e3an\uff0c\u6a21\u5f0f\u4e32\u957f\u5ea6\u4e3am\uff0c\u5219\u6734\u7d20\u7b97\u6cd5\u590d\u6742\u5ea6\u662fo\uff08nm\uff09\uff0ckmp\u7b97\u6cd5\u5176\u5b9e\u5c31\u662f\u5bf9\u6734\u7d20\u7b97\u6cd5\u7684\u4f18\u5316\uff1a\u5f53\u5339\u914d\u8fc7\u7a0b\u4e2d\u51fa\u73b0\u5931\u914d\u7684\u60c5\u51b5\u65f6\uff0c\u53ef\u4ee5\u8df3\u8fc7\u5c0f\u4e8e\u6a21\u5f0f\u4e32\u7684\u957f\u5ea6\u518d\u8fdb\u884c\u5339\u914d\uff0c\u9700\u8981\u8ba1\u7b97\u8bb0\u5f55\u56de\u6587\u957f\u5ea6\u7684\u524d\u7f00\u8868\u505a\u5230\u3002<\/strong><\/p>\n\n\n\n \u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n T1 \u6c42\u7b2cK\u5c0f\u7684\u6570\uff08\u5206\u6cbb\uff09 \u9898\u76ee\uff1a \u7528\u5230\u7c7b\u4f3c\u5feb\u901f\u6392\u5e8f\u7684\u5206\u6cbb\u6cd5\u3002\u5feb\u901f\u6392\u5e8f\u7684\u601d\u60f3\u662f\u628a\u6570\u591a\u6b21\u5206\u4e3a\u4e09\u4e2a\u533a\u95f4\uff08\u5c0f\u4e8e\u57fa\u51c6\u6570 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-195","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=195"}],"version-history":[{"count":2,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/195\/revisions"}],"predecessor-version":[{"id":202,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/195\/revisions\/202"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\/\/qsort (\u5feb\u901f\u6392\u5e8f\u7684\u6838\u5fc3\u601d\u60f3\u662f\u9012\u5f52\u5206\u6cbb\uff09\r\n#include <iostream>\r\nusing namespace std;\r\nconst int maxx = 100005;\r\nint n,k,a[maxx],b[maxx],c[maxx],d[maxx];\r\nvoid prework(){\r\n\tcin>>n;\r\n\tfor(int i=1;i<=n;i++){\r\n\t\tcin>>a[i];\r\n\t}\r\n}\r\nvoid qsort(int l,int r){\r\n\tif(l>=r){\r\n\t\treturn;\r\n\t\t\/\/len <= 0 \r\n\t}\r\n\tint t1=0,t2=0,t3=0,mid;\r\n\tmid = a[(l+r)\/2];\r\n\tfor(int i=l;i<=r;i++){\r\n\t\tif(a[i]<mid)\r\n\t\t\tb[++t1] = a[i];\r\n\t\telse if(a[i]==mid)\r\n\t\t\tc[++t2] = a[i];\r\n\t\telse d[++t3] = a[i];\r\n\t}\r\n\tfor(int i=1;i<=t1;i++)\r\n\t\ta[i+l-1] = b[i];\r\n\tfor(int i=1;i<=t2;i++)\r\n\t\ta[i+t1+l-1] = c[i];\r\n\tfor(int i=1;i<=t3;i++)\r\n\t\ta[i+t1+t2+l-1] = d[i];\r\n\t\r\n\tqsort(l,l+t1-1);\r\n\tqsort(l+t1+t2,r);\r\n}\r\nvoid solve(){\r\n\tqsort(1,n);\r\n\tfor(int i=1;i<=n;i++) cout<<a[i]<<' ';\r\n}\r\nint main(){\r\n\tprework();\r\n\tsolve();\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n#include <iostream>\r\nusing namespace std;\r\nconst int maxx = 5e6+5;\r\nint n,k,a[maxx],b[maxx],c[maxx],d[maxx],ans;\r\nvoid prework(){\r\n\tcin>>n>>k;\r\n\tfor(int i=0;i<n;i++){\r\n\t\tcin>>a[i];\r\n\t}\r\n}\r\nvoid qsort(int l,int r){\r\n\tif(l>=r){\r\n\t\tans = a[l];\/\/\u8fb9\u754c\u60c5\u51b5\u66f4\u65b0\u7b54\u6848(\u5f53l==r\u65f6\u4f1a\u76f4\u63a5\u9000\u51fa\r\n\t\treturn;\r\n\t}\r\n\tint t1=0,t2=0,t3=0,mid;\r\n\tmid = a[(l+r)\/2];\r\n\tfor(int i=l;i<=r;i++){\r\n\t\tif(a[i]<mid)\r\n\t\t\tb[++t1] = a[i];\r\n\t\telse if(a[i]==mid)\r\n\t\t\tt2++;\/\/c[++t2] = a[i];\r\n\t\telse\r\n\t\t\td[++t3] = a[i];\r\n\t}\r\n\t\/\/\u5206\u6210\u4e09\u4e2a\u533a\u95f4 L~i~j~R k<=i\u65f6 \u53bb\u641c\u5de6\u8fb9\u7684\u533a\u95f4\r\n\tif(l+t1-1>=k){\r\n\t\tfor(int i=0;i<t1;i++)\r\n\t\t\ta[l+i] = b[i+1];\/\/fill left\r\n\t\tqsort(l,l+t1-1);\r\n\t}\r\n\telse if(l+t1+t2<=k){\r\n\t\tfor(int i=0;i<t3;i++)\r\n\t\t\ta[l+t1+t2+i] = d[i+1];\r\n\t\tqsort(l+t1+t2,r);\r\n\t}\r\n\telse{\r\n\t\tans = mid;\/\/\u66f4\u65b0\u7b54\u6848\r\n\t\treturn;\r\n\t}\r\n}\r\nvoid solve(){\r\n\tqsort(0,n-1);\r\n\tcout<<ans;\r\n}\r\nint main(){\r\n\tios::sync_with_stdio(false);\r\n\tcin.tie(NULL); cout.tie(NULL);\r\n\tprework();\r\n\tsolve();\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\nT2 \u7a7f\u8d8a\u96f7\u533a<\/h2>\n\n\n\n
![\"\"](\"https:\/\/forelink.top\/wp-content\/uploads\/2023\/05\/image-52-1024x1010.png\")
<\/div><\/figure>\n\n\n\n![\"\"](\"https:\/\/forelink.top\/wp-content\/uploads\/2023\/05\/image-53-1024x443.png\")
<\/div><\/figure>\n\n\n\n#include <iostream>\n#include <queue>\nusing namespace std;\nstruct point{\n\tint x,y,k;\n};\nint movex[5]={0,1,-1,0,0};\nint movey[5]={0,0,0,1,-1};\nint n,world[105][105],ans=-1;\nbool vis[105][105];\nqueue<point> a;\nbool judge(int x,int y,int nx,int ny){\n\tif(world[nx][ny]==2)\n\t\treturn true;\n\telse if(world[x][y]==world[nx][ny])\n\t\treturn false;\n\treturn true;\n}\nvoid bfs(){\n\twhile(!a.empty()){\n\t\tpoint temp = a.front();\n\t\tint x1=temp.x,y1=temp.y,k1=temp.k;\n\n\t\tif(world[x1][y1]==2){\n\t\t\tans = k1;\n\t\t\treturn;\n\t\t}\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tint nx=x1+movex[i];\n\t\t\tint ny=y1+movey[i];\n\t\t\tif(nx>=1&&nx<=n&&ny>=1&&ny<=n&&judge(x1,y1,nx,ny)&&vis[nx][ny]==0){\n\t\t\t\tvis[nx][ny]=1;\n\t\t\t\ta.push({nx,ny,k1+1});\n\t\t\t}\n\t\t}\n\t\ta.pop();\n\t}\n}\nvoid prework(){\n\tcin>>n;\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int j=1;j<=n;j++){\n\t\t\tchar temp; cin>>temp;\n\t\t\tif(temp=='B')\n\t\t\t\tworld[i][j]=2;\n\t\t\telse if(temp=='A')\n\t\t\t\tworld[i][j]=3,vis[i][j]=1,a.push({i,j,0});\n\t\t\telse if(temp=='+')\n\t\t\t\tworld[i][j]=1;\n\t\t\telse\n\t\t\t\tworld[i][j]=0;\n\t\t}\n\t}\n}\nint main(){\n\tprework();\n\tbfs();\n\tcout<<ans;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\nT3 KMP\u5b57\u7b26\u4e32\u5339\u914d (\u6a21\u677f\uff09<\/h2>\n\n\n\n
![\"\"](\"https:\/\/forelink.top\/wp-content\/uploads\/2023\/05\/image-54-1024x596.png\")
<\/div><\/figure>\n\n\n\n![\"\"](\"https:\/\/forelink.top\/wp-content\/uploads\/2023\/05\/image-55-1024x897.png\")
<\/div><\/figure>\n\n\n\n#include <iostream>\r\n#include <cstring>\r\nusing namespace std;\r\nconst int l = 1000005;\r\nint next_[l],ans,l1,l2;\r\nchar t[l],p[l];\r\nstring s1,s2;\r\nvoid trans(){\r\n\tl1 = s1.length();\r\n\tl2 = s2.length();\r\n\tfor(int i=0;i<l1;i++){\r\n\t\tt[i+1] = s1[i];\r\n\t\tif(i<l2) p[i+1] = s2[i];\r\n\t}\r\n}\r\nvoid prefix(){\r\n\tint k=0;\r\n\tfor(int i=2;i<=l2;i++){\r\n\t\twhile(k>0 && p[k+1]!=p[i])\r\n\t\t\tk = next_[k];\r\n\t\tif(p[k+1]==p[i])\r\n\t\t\tk++;\r\n\t\tnext_[i]=k;\/\/\u66f4\u65b0next_\u524d\u7f00\u8868\r\n\t}\r\n}\r\n\r\nvoid kmp(){\r\n\tint k=0;\r\n\tfor(int i=1;i<=l1;i++){\r\n\t\twhile(k>0 && p[k+1]!=t[i]){\r\n\t\t\tk = next_[k];\r\n\t\t}\r\n\t\tif(p[k+1]==t[i])\r\n\t\t\tk++;\r\n\t\tif(k==l2){\r\n\t\t\tcout<<i-l2+1<<endl;\r\n\t\t\tk=next_[k];\r\n\t\t}\r\n\t}\r\n}\r\nint main(){\r\n\tcin>>s1>>s2;\r\n\ttrans();\r\n\tprefix();\r\n\tkmp();\r\n\tfor(int i=1;i<=l2;i++) \r\n\tcout<<next_[i]<<' ';\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"