{"id":378,"date":"2020-04-22T00:37:35","date_gmt":"2020-04-21T16:37:35","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=378"},"modified":"2020-07-12T20:59:37","modified_gmt":"2020-07-12T12:59:37","slug":"ac%e8%87%aa%e5%8a%a8%e6%9c%ba-%e4%be%8b%e9%a2%98","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/22\/ac%e8%87%aa%e5%8a%a8%e6%9c%ba-%e4%be%8b%e9%a2%98\/","title":{"rendered":"AC\u81ea\u52a8\u673a \u4f8b\u9898"},"content":{"rendered":"

\u6d1b\u8c37 P3699<\/a><\/h4>\n

\u8f93\u5165n\u4e2a\u5355\u8bcd\uff0c\u6c42\u6bcf\u4e2a\u5355\u8bcd\u5728\u6240\u6709\u5355\u8bcd\u4e2d\u51fa\u73b0\u7684\u6b21\u6570\u3002
\n\u6784\u9020AC\u81ea\u52a8\u673a\uff0ctopu\u6392\u5e8f\u3002<\/p>\n

#include <bits\/stdc++.h>\nusing namespace std;\nconst int maxn = 1e6+5;\ntypedef struct AC{\n    int Trie[maxn][27],fail[maxn],mp[maxn],cnt;\n    int times[maxn],in[maxn];\n    void Insert(char *s,int len,int idx);\n    void build();\n    void topu();\n    void output();\n}AC_auto;\nint n;\nchar s[maxn];\nAC_auto ac;\nint main(){\n    scanf ("%d",&n);\n    for (int i=1;i<=n;i++){\n        scanf ("%s",s+1);\n        ac.Insert(s,strlen(s+1),i);\n    }\n    ac.build();\n    ac.output();\n    return 0;\n}\nvoid AC_auto::Insert(char *s,int len,int idx){\n    int root = 0;\n    for (int i=1;i<=len;i++){\n        if (!Trie[root][s[i]-'a'+1])    Trie[root][s[i]-'a'+1] = ++cnt;\n        root = Trie[root][s[i]-'a'+1];\n        times[root]++;\n    }\n    mp[idx] = root;\n    return;\n}\nvoid AC_auto::build(){\n    queue<int> q;\n    for (int i=1;i<=26;i++) if (Trie[0][i])\n        q.push(Trie[0][i]);\n    while (!q.empty()){\n        int temp = q.front();   q.pop();\n        for (int i=1;i<=26;i++){\n            if (Trie[temp][i]){\n                fail[Trie[temp][i]] = Trie[fail[temp]][i];\n                in[Trie[fail[temp]][i]]++;\n                q.push(Trie[temp][i]);\n            }else\n                Trie[temp][i] = Trie[fail[temp]][i];\n        }\n    }\n    topu();\n    return;\n}\nvoid AC_auto::topu(){\n    queue<int> q;\n    for (int i=1;i<=cnt;i++)    if (in[i]==0)\n        q.push(i);\n    while (!q.empty()){\n        int temp = q.front();   q.pop();\n        times[fail[temp]] += times[temp];\n        in[fail[temp]]--;\n        if (in[fail[temp]]==0)\n            q.push(fail[temp]);\n    }\n    return;\n}\nvoid AC_auto::output(){\n    for (int i=1;i<=n;i++)\n        printf ("%d\\n",times[mp[i]]);\n    return;\n}<\/code><\/pre>\n
CSES1731 Word Combinations<\/a><\/h4>\n
\u7ed9\u4e00\u4e2a\u6bcd\u4e32s\u548c\u82e5\u5e72\u4e2a\u6a21\u677f\u4e32\uff0c\u6c42\u7528\u8fd9\u4e9b\u6a21\u677f\u4e32\u53ef\u4ee5\u6709\u591a\u5c11\u79cd\u65b9\u5f0f\u7ec4\u5408\u6210\u6bcd\u4e32\u3002\u7ed3\u679c\u5bf91e9+7\u53d6\u6a21\u3002<\/p>\n
\u601d\u8def\uff1a\u5bf9\u6a21\u677f\u4e32\u5efa\u7acbAC\u81ea\u52a8\u673a\u3002dp[i]\u8868\u793as\u7684\u524di\u4e2a\u5b57\u7b26\u6709\u591a\u5c11\u79cd\u7ec4\u5408\u65b9\u5f0f\u3002<\/p>\n
\u7136\u540e\u7528\u6bcd\u4e32\u8dd1\u4e00\u904d\u81ea\u52a8\u673a\uff0c\u82e5\u6bcd\u4e32\u626b\u63cf\u5230s[i]\u65f6\uff0c\u81ea\u52a8\u673a\u4e0a\u626b\u63cf\u5230\u7b2cx\u4e2a\u7ed3\u70b9\uff0c\u6211\u4eec\u77e5\u9053x\u7ed3\u70b9\u5bf9\u5e94\u7684\u5b57\u7b26\u4e32\u662f\u5b50\u4e32s[1...i]\u7684\u6700\u957f\u540e\u7f00\uff0c\u7136\u540e\u6cbf\u7740fail\u8fb9\u6bcf\u4e00\u4e2a\u7ed3\u70b9\u90fd\u662f\u4e00\u4e2a\u540e\u7f00\uff0c\u76f4\u81f3\u8d70\u52300\u7ed3\u70b9\u3002\u90a3\u4e48\u5c31\u66b4\u529b\u8df3fail\u8fb9\uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u540e\u7f00\u7ed3\u70b9x(x\u5fc5\u987b\u88ab\u6807\u8bb0\u4e3a\u662f\u4e00\u4e2a\u6a21\u677f\u4e32)\uff0c\u6709\uff1adp[i] += dp[i-Len[xx]]<\/code><\/p>\n
\u521d\u59cb\u5316dp[0] = 1.<\/p>\n
\u4ee3\u7801\uff1a<\/p>\n
#include <bits\/stdc++.h>\nusing namespace std;\nconst int maxn = 1e6+5, mod = 1e9+7;\nstruct AC_Auto{\n    int Trie[maxn][27], fail[maxn], Len[maxn], cnt;\n    int vis[maxn];\n    AC_Auto(){\n        cnt = 0;\n    }\n    void insert(char *s, int len);\n    void build();\n    void query(char *s, int len);\n}A;\nchar s[5005], t[maxn];\nint n, len, dp[5005];\n\nint main(){\n    scanf ("%s %d", s+1, &n);\n    len = strlen(s+1);\n    for (int i=1; i<=n; i++){\n        scanf ("%s", t+1);\n        A.insert(t, strlen(t+1));\n    }\n    A.build();\n    dp[0] = 1;\n    A.query(s, len);\n    printf ("%d", dp[len]);\n    return 0;\n}\nvoid AC_Auto::insert(char *s, int len){\n    int root = 0;\n    for (int i=1; i<=len; i++){\n        if (!Trie[root][s[i]-'a'+1])    Trie[root][s[i]-'a'+1] = ++cnt;\n        root = Trie[root][s[i]-'a'+1];\n    }\n    Len[root] = len;\n    vis[root] = 1;\n    return;\n}\nvoid AC_Auto::build(){\n    queue<int> q;\n    for (int i=1; i<=26; i++)   if (Trie[0][i])\n        q.push(Trie[0][i]);\n    while (!q.empty()){\n        int tmp = q.front();    q.pop();\n        for (int i=1; i<=26; i++){\n            if (Trie[tmp][i]){\n                fail[Trie[tmp][i]] = Trie[fail[tmp]][i];\n                q.push(Trie[tmp][i]);\n            }else{\n                Trie[tmp][i] = Trie[fail[tmp]][i];\n            }\n        }\n    }\n    return;\n}\nvoid AC_Auto::query(char *s, int len){\n    int root = 0, tmp;\n    for (int i=1; i<=len; i++){\n        root = Trie[root][s[i]-'a'+1];\n        tmp = root;\n        while (tmp){\n            if (vis[tmp])\n                dp[i] = (dp[i]+dp[i-Len[tmp]])%mod;\n            tmp = fail[tmp];\n        }\n    }\n    return;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6d1b\u8c37 P3699 \u8f93\u5165n\u4e2a\u5355\u8bcd\uff0c\u6c42\u6bcf\u4e2a\u5355\u8bcd\u5728\u6240\u6709\u5355\u8bcd\u4e2d\u51fa\u73b0\u7684\u6b21\u6570\u3002 \u6784\u9020AC\u81ea\u52a8\u673a\uff0ctopu\u6392\u5e8f\u3002  […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[11],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/378"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=378"}],"version-history":[{"count":4,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/378\/revisions"}],"predecessor-version":[{"id":704,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/378\/revisions\/704"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=378"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=378"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=378"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}