{"id":5379,"date":"2021-07-09T21:41:41","date_gmt":"2021-07-09T13:41:41","guid":{"rendered":"https:\/\/damogame.cn\/wordpress\/?p=5379"},"modified":"2021-07-09T21:41:41","modified_gmt":"2021-07-09T13:41:41","slug":"ac%e8%87%aa%e5%8a%a8%e6%9c%ba-%e7%ae%97%e6%b3%95%e8%af%a6%e8%a7%a3%e5%9b%be%e8%a7%a3%e5%8f%8a%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/5379","title":{"rendered":"AC\u81ea\u52a8\u673a \u7b97\u6cd5\u8be6\u89e3(\u56fe\u89e3)\u53ca\u6a21\u677f"},"content":{"rendered":"

\u539f\u6587\u5730\u5740<\/a><\/p>\n

 <\/p>\n

bestsort 2018-10-05 22:17:32 71571 \u6536\u85cf 309
\n\u5206\u7c7b\u4e13\u680f\uff1a \u5b57\u7b26\u4e32 \u6570\u636e\u7ed3\u6784 \u901a\u4fd7\u6613\u61c2\u7cfb\u5217 \u6587\u7ae0\u6807\u7b7e\uff1a AC\u81ea\u52a8\u673a \u591a\u6a21\u5f0f\u4e32\u5339\u914d \u6587\u672c\u5904\u7406
\n\u7248\u6743
\n\u8981\u5b66AC\u81ea\u52a8\u673a\u9700\u8981\u81ea\u5907\u4e24\u4e2a\u524d\u7f6e\u6280\u80fd:KMP\u548ctrie\u6811(\u5176\u5b9e\u4e2a\u4eba\u611f\u89c9\u4e0d\u4f1akmp\u4e5f\u884c,\u5931\u914d\u6307\u9488\u7684\u6982\u5ff5\u5e76\u4e0d\u96be)
\n\u5176\u4e2d,KMP\u662f\u7528\u4e8e\u4e00\u5bf9\u4e00\u7684\u5b57\u7b26\u4e32\u5339\u914d,\u800ctrie\u867d\u7136\u80fd\u7528\u4e8e\u591a\u6a21\u5f0f\u5339\u914d,\u4f46\u662f\u6bcf\u6b21\u5339\u914d\u5931\u8d25\u90fd\u9700\u8981\u8fdb\u884c\u56de\u6eaf,\u5982\u679c\u6a21\u5f0f\u4e32\u5f88\u957f\u7684\u8bdd\u4f1a\u5f88\u6d6a\u8d39\u65f6\u95f4,\u6240\u4ee5AC\u81ea\u52a8\u673a\u5e94\u8fd0\u800c\u751f,\u5982\u540cManacher\u4e00\u6837,AC\u81ea\u52a8\u673a\u5229\u7528\u67d0\u4e9b\u64cd\u4f5c\u963b\u6b62\u4e86\u6a21\u5f0f\u4e32\u5339\u914d\u9636\u6bb5\u7684\u56de\u6eaf,\u5c06\u65f6\u95f4\u590d\u6742\u5ea6\u4f18\u5316\u5230\u4e86O ( n ) O(n)O(n)(n)\u4e3a\u6587\u672c\u4e32\u957f\u5ea6<\/p>\n

\u8f6c\u8f7d\u6ce8\u660e\u51fa\u81eabestsort.cn,\u8c22\u8c22\u5408\u4f5c<\/p>\n

\u5927\u5bb6\u56de\u590d\u8bf7\u53bbbestsort.cn\u56de\u590d\u5427\uff0cCSDN\u6211\u6bcf\u6b21\u90fd\u4e0d\u77e5\u9053\u4f60\u4eec\u56de\u590d\u7684\u697c\u5c42\u5728\u54ea…\u70b9\u51fb\u67e5\u770b\u8bc4\u8bba\u5b83\u90fd\u4e0d\u5e26\u81ea\u52a8\u8df3\u8f6c\u7684QAQ
\n\u4e0b\u9762\u5f00\u59cb\u7528\u56fe\u5b66\u4e60ac\u81ea\u52a8\u673a\u5427(\u4e2a\u4eba\u6bd4\u8f83\u559c\u6b22\u653e\u56fe,\u80fd\u7528\u4e00\u5f20\u56fe\u89e3\u51b3\u7684\u7edd\u4e0d\u53e8\u53e8)
\n\u9996\u5148\u7ed9\u5b9a\u6a21\u5f0f\u4e32”ash”,”shex”,”bcd”,”sha”,\u7136\u540e\u6211\u4eec\u6839\u636e\u6a21\u5f0f\u4e32\u5efa\u7acb\u5982\u4e0btrie\u6811:<\/p>\n

 <\/p>\n

\u7136\u540e\u6211\u4eec\u518d\u4e86\u89e3\u4e0b\u4e00\u6b65:
\nac\u81ea\u52a8\u673a,\u5c31\u662f\u5728tire\u6811\u7684\u57fa\u7840\u4e0a,\u589e\u52a0\u4e00\u4e2afail\u6307\u9488,\u5982\u679c\u5f53\u524d\u70b9\u5339\u914d\u5931\u8d25,\u5219\u5c06\u6307\u9488\u8f6c\u79fb\u5230fail\u6307\u9488\u6307\u5411\u7684\u5730\u65b9,\u8fd9\u6837\u5c31\u4e0d\u7528\u56de\u6eaf,\u800c\u53ef\u4ee5\u8def\u5339\u914d\u4e0b\u53bb\u4e86.(\u5f53\u524d\u6a21\u5f0f\u4e32\u540e\u7f00\u548cfail\u6307\u9488\u6307\u5411\u7684\u6a21\u5f0f\u4e32\u90e8\u5206\u524d\u7f00\u76f8\u540c,\u5982abce\u548cbcd,\u6211\u4eec\u627e\u5230c\u53d1\u73b0\u4e0b\u4e00\u4e2a\u8981\u627e\u7684\u4e0d\u662fe,\u5c31\u8df3\u5230bcd\u4e2d\u7684c\u5904,\u770b\u770b\u6b64\u5904\u7684\u4e0b\u4e00\u4e2a\u5b57\u7b26(d)\u662f\u4e0d\u662f\u5e94\u8be5\u627e\u7684\u90a3\u4e00\u4e2a)<\/p>\n

\u4e00\u822c,fail\u6307\u9488\u7684\u6784\u5efa\u90fd\u662f\u7528bfs\u5b9e\u73b0\u7684
\n\u9996\u5148\u6bcf\u4e2a\u6a21\u5f0f\u4e32\u7684\u9996\u5b57\u6bcd\u80af\u5b9a\u662f\u6307\u5411\u6839\u8282\u70b9\u7684(\u4e00\u4e2a\u5b57\u6bcd\u4f60\u778e\u6307\u4ec0\u4e48\u6307,\u6307\u4e86\u4e5f\u662f\u5934\u5b57\u6bcd\u6709\u4ec0\u4e48\u7528\u561b)<\/p>\n

\u73b0\u5728\u7b2c\u4e00\u5c42bfs\u904d\u5386\u5b8c\u4e86,\u5f00\u59cb\u7b2c\u4e8c\u5c42
\n(\u6839\u8282\u70b9\u4e3a\u7b2c0\u5c42)\u7b2c\u4e8c\u5c42a\u7684\u5b50\u8282\u70b9\u4e3as,\u4f46\u662f\u6211\u4eec\u8fd8\u662f\u8981\u4ecea-z\u904d\u5386,\u5982\u679c\u4e0d\u5b58\u5728\u8fd9\u4e2a\u5b50\u8282\u70b9\u6211\u4eec\u5c31\u8ba9\u4ed6\u6307\u5411\u6839\u8282\u70b9(\u5982\u4e0b\u56fe\u7ea2\u8272\u7684a)<\/p>\n

\u5f53\u6211\u4eec\u904d\u5386\u5230s\u7684\u65f6\u5019,\u7531\u4e8e\u5b58\u5728s\u8fd9\u4e2a\u8282\u70b9,\u6211\u4eec\u5c31\u8ba9\u4ed6\u7684fail\u6307\u9488\u6307\u5411\u4ed6\u7236\u4eb2\u8282\u70b9(a)\u7684fail\u6307\u9488\u6307\u5411\u7684\u90a3\u4e2a\u8282\u70b9(\u6839)\u7684\u5177\u6709\u76f8\u540c\u5b57\u6bcd\u7684\u5b50\u8282\u70b9(\u7b2c\u4e00\u5c42\u7684s),\u4e5f\u5c31\u662f\u8fd9\u6837<\/p>\n

\u6309\u7167\u76f8\u540c\u89c4\u5f8b\u6784\u5efa\u7b2c\u4e8c\u5c42\u540e,\u5230\u4e86\u7b2c\u4e09\u5c42\u7684h\u70b9,\u8fd8\u662f\u6309\u7167\u4e0a\u9762\u7684\u89c4\u5219,\u6211\u4eec\u627e\u5230h\u7684\u7236\u4eb2\u8282\u70b9(s)fail\u6307\u9488\u6307\u5411\u7684\u90a3\u4e2a\u4f4d\u7f6e(\u7b2c\u4e00\u5c42\u7684s)\u7136\u540e\u6307\u5411\u5b83\u6240\u6307\u5411\u7684\u76f8\u540c\u5b57\u6bcd\u6839->s->h\u7684\u8fd9\u4e2a\u94fe\u7684h\u8282\u70b9,\u5982\u4e0b\u56fe<\/p>\n

\u5b8c\u5168\u6784\u9020\u597d\u540e\u7684\u6811<\/p>\n

\u7136\u540e\u5339\u914d\u5c31\u5f88\u7b80\u5355\u4e86,\u8fd9\u91cc\u4ee5ashe\u4e3a\u4f8b
\n\u6211\u4eec\u5148\u7528ash\u5339\u914d,\u5230h\u4e86\u53d1\u73b0:\u8bf6\u8fd9\u91ccash\u662f\u4e00\u4e2a\u5b8c\u6574\u7684\u6a21\u5f0f\u4e32,\u597d\u7684ans++,\u7136\u540e\u627e\u4e0b\u4e00\u4e2ae,\u53ef\u662fash\u540e\u9762\u6ca1\u5b57\u6bcd\u4e86\u554a,\u6211\u4eec\u5c31\u8df3\u5230hfail\u6307\u9488\u6307\u5411\u7684\u90a3\u4e2ah\u7ee7\u7eed\u627e,\u8fd8\u662f\u6ca1\u6709?\u518d\u8df3,\u7ed3\u679c\u5f53\u524d\u7684h\u6307\u5411\u7684\u662f\u6839\u8282\u70b9,\u53c8\u4ece\u6839\u8282\u70b9\u627e,\u7136\u800c\u8fd8\u662f\u6ca1\u6709\u627e\u5230e,\u7a0b\u5e8fEND<\/p>\n

\u8fc7\u7a0b\u5982\u4e0b\u56fe<\/p>\n

\u559c\u95fb\u4e50\u89c1\u6a21\u677f\u7cfb\u5217<\/p>\n

#include <queue>
\n#include <cstdlib>
\n#include <cmath>
\n#include <cstdio>
\n#include <string>
\n#include <cstring>
\n#include <iostream>
\n#include <algorithm>
\nusing namespace std;
\ntypedef long long ll;
\nconst int maxn = 2*1e6+9;<\/p>\n

int trie[maxn][26]; \/\/\u5b57\u5178\u6811
\nint cntword[maxn]; \/\/\u8bb0\u5f55\u8be5\u5355\u8bcd\u51fa\u73b0\u6b21\u6570
\nint fail[maxn]; \/\/\u5931\u8d25\u65f6\u7684\u56de\u6eaf\u6307\u9488
\nint cnt = 0;<\/p>\n

void insertWords(string s){
\nint root = 0;
\nfor(int i=0;i<s.size();i++){
\nint next = s[i] – ‘a’;
\nif(!trie[root][next])
\ntrie[root][next] = ++cnt;
\nroot = trie[root][next];
\n}
\ncntword[root]++; \/\/\u5f53\u524d\u8282\u70b9\u5355\u8bcd\u6570+1
\n}
\nvoid getFail(){
\nqueue <int>q;
\nfor(int i=0;i<26;i++){ \/\/\u5c06\u7b2c\u4e8c\u5c42\u6240\u6709\u51fa\u73b0\u4e86\u7684\u5b57\u6bcd\u6254\u8fdb\u961f\u5217
\nif(trie[0][i]){
\nfail[trie[0][i]] = 0;
\nq.push(trie[0][i]);
\n}
\n}<\/p>\n

\/\/fail[now] ->\u5f53\u524d\u8282\u70b9now\u7684\u5931\u8d25\u6307\u9488\u6307\u5411\u7684\u5730\u65b9
\ntire[now][i] -> \u4e0b\u4e00\u4e2a\u5b57\u6bcd\u4e3ai+’a’\u7684\u8282\u70b9\u7684\u4e0b\u6807\u4e3atire[now][i]
\nwhile(!q.empty()){
\nint now = q.front();
\nq.pop();<\/p>\n

for(int i=0;i<26;i++){ \/\/\u67e5\u8be226\u4e2a\u5b57\u6bcd
\nif(trie[now][i]){
\n\/\/\u5982\u679c\u6709\u8fd9\u4e2a\u5b50\u8282\u70b9\u4e3a\u5b57\u6bcdi+’a’,\u5219
\n\/\/\u8ba9\u8fd9\u4e2a\u8282\u70b9\u7684\u5931\u8d25\u6307\u9488\u6307\u5411(((\u4ed6\u7236\u4eb2\u8282\u70b9)\u7684\u5931\u8d25\u6307\u9488\u6240\u6307\u5411\u7684\u90a3\u4e2a\u8282\u70b9)\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9)
\n\/\/\u6709\u70b9\u7ed5,\u4e3a\u4e86\u65b9\u4fbf\u7406\u89e3\u7279\u610f\u52a0\u4e86\u62ec\u53f7<\/p>\n

fail[trie[now][i]] = trie[fail[now]][i];
\nq.push(trie[now][i]);
\n}
\nelse\/\/\u5426\u5219\u5c31\u8ba9\u5f53\u524d\u8282\u70b9\u7684\u8fd9\u4e2a\u5b50\u8282\u70b9
\n\/\/\u6307\u5411\u5f53\u524d\u8282\u70b9fail\u6307\u9488\u7684\u8fd9\u4e2a\u5b50\u8282\u70b9
\ntrie[now][i] = trie[fail[now]][i];
\n}
\n}
\n}<\/p>\n

int query(string s){
\nint now = 0,ans = 0;
\nfor(int i=0;i<s.size();i++){ \/\/\u904d\u5386\u6587\u672c\u4e32
\nnow = trie[now][s[i]-‘a’]; \/\/\u4eces[i]\u70b9\u5f00\u59cb\u5bfb\u627e
\nfor(int j=now;j && cntword[j]!=-1;j=fail[j]){
\n\/\/\u4e00\u76f4\u5411\u4e0b\u5bfb\u627e,\u76f4\u5230\u5339\u914d\u5931\u8d25(\u5931\u8d25\u6307\u9488\u6307\u5411\u6839\u6216\u8005\u5f53\u524d\u8282\u70b9\u5df2\u627e\u8fc7).
\nans += cntword[j];
\ncntword[j] = -1; \/\/\u5c06\u904d\u5386\u56fd\u540e\u7684\u8282\u70b9\u6807\u8bb0,\u9632\u6b62\u91cd\u590d\u8ba1\u7b97
\n}
\n}
\nreturn ans;
\n}<\/p>\n

int main() {
\nint n;
\nstring s;
\ncin >> n;
\nfor(int i=0;i<n;i++){
\ncin >> s ;
\ninsertWords(s);
\n}
\nfail[0] = 0;
\ngetFail();
\ncin >> s ;
\ncout << query(s) << endl;
\nreturn 0;
\n}<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

\u539f\u6587\u5730\u5740   bestsort<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[119],"class_list":["post-5379","post","type-post","status-publish","format-standard","hentry","tag-03-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5379","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=5379"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5379\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=5379"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=5379"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=5379"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}