{"id":1386,"date":"2021-02-27T20:58:33","date_gmt":"2021-02-27T12:58:33","guid":{"rendered":"http:\/\/47.101.202.111\/?p=1386"},"modified":"2021-03-07T00:17:15","modified_gmt":"2021-03-06T16:17:15","slug":"algorithm-string-trie","status":"publish","type":"post","link":"http:\/\/139.196.114.170\/?p=1386","title":{"rendered":"Trie\u6811 – \u4ee3\u7801\u8865\u5168\u548c\u641c\u7d22\u63d0\u793a\u5b9e\u73b0"},"content":{"rendered":"

Trie<\/h2>\n

\u524d\u7f00\u6811\u662f\u4e00\u4e2aN\u53c9\u6811<\/p>\n

\u5b57\u7b26\u4e32\u95f4\u76f8\u540c\u524d\u7f00\u662f\u540c\u4e00\u8def\u5f84<\/p>\n

\u7528\u4e8e\u9884\u6d4b\u5b57\u7b26\u4e32\u3001\u5b57\u7b26\u4e32\u5b58\u53d6\u3001\u62fc\u5199\u68c0\u67e5\u548c\u8bcd\u9891\u7edf\u8ba1\u7b49<\/p>\n

\u7c7b\u5b9e\u73b0<\/h2>\n

\u6570\u7ec4\u8282\u70b9<\/h3>\n
\nclass Trie\n{\n    private:\n        Trie *child[26];\n        int num;\n\n    public:\n        Trie(){ num = 0; memset(child, 0, sizeof(child)); };\n        int get(string s);\n        void put(string s);\n};\n<\/pre>\n
\u8fed\u4ee3\u5b58\u50a8\u7edf\u8ba1\u524d\u7f00\u6570\u76ee<\/h4>\n
void Trie::put(string s)\n{\n    Trie *p = this;\n    for (int i = 0; s[i]; i++)\n    {\n        int ch = s[i] - 'a';\n        if (p->child[ch] == nullptr)\n            p->child[ch] = new Trie();\n        p->num++;\n        p = p->child[c];\n    }\n}\n<\/code><\/pre>\n
\u8fed\u4ee3\u5339\u914d\u524d\u7f00\u6570<\/h4>\n
int Trie::get(string s)\n{\n    Trie *p = this;\n    for (int i = 0; s[i]; i++)\n    {\n        int ch = s[i] - 'a';\n        if (p->child[ch] == nullptr)\n            return 0;\n        p = p->child[ch];\n    }\n    return p->num;\n}\n<\/code><\/pre>\n
map\u8282\u70b9<\/h3>\n
\nstruct Node\n{\n    unordered_map map;\n    int num;\n};\n\nclass Trie\n{\n    private:\n        Node *root;\n        void put(Node *n, string s, int i);\n        int get(Node *n, string s, int i);\n\n    public:\n        Trie() { root = new Node(); }\n        void put(string s);\n        int get(string s);\n};\n<\/pre>\n
\u9012\u5f52\u5b58\u50a8\u7edf\u8ba1<\/h4>\n
void Trie::put(string s) { put(root, s, 0); };\n\nvoid Trie::put(Node *n, string s, int i)\n{\n    n->num++;\n    if (!s[i]) return;\n    if (n->map.count(s[i]) <= 0)\n        n->map[s[i]] = new Node();\n    n = n->map[s[i]];\n    put(n, s, ++i);\n}\n<\/code><\/pre>\n
\u9012\u5f52\u53d6\u51fa\u7edf\u8ba1<\/h4>\n
int Trie::get(string s) { return get(root, s, 0); };\n\nint Trie::get(Node *n, string s, int i)\n{\n    if (!s[i] && i != 0) return n->num;\n    if (n->map.count(s[i]) <= 0) return 0;\n    n = n->map[s[i]];\n    return get(n, s, ++i);\n}\n<\/code><\/pre>\n
\u6570\u7ec4\u5b9e\u73b0<\/h2>\n
\u96640\u884c\u6bcf\u4e2a\u5143\u7d20\u8868\u793a\u5bf9\u5e94\u5355\u5b57\u7b26\u524d\u7f00\u7684\u7236\u8282\u70b9\u5916\uff0c\u6570\u7ec4\u6bcf\u884c\u5747\u4ee3\u8868\u4e00\u4e2a\u5b50\u8282\u70b9\uff0c\u6bcf\u65b0\u589e\u4e00\u4e2a\u5b50\u8282\u70b9\u5c31\u5b58\u5728\u6570\u7ec4\u4e0b\u4e00\u884c\u4e2d\uff0c\u7236\u8282\u70b9\u901a\u8fc7\u5b50\u8282\u70b9\u884c\u7d22\u5f15\u94fe\u63a5\u5b50\u8282\u70b9\uff0c\u76f8\u6bd4\u7c7b\u5b9e\u73b0\u66f4\u7701\u5185\u5b58<\/p>\n
\u5b50\u94fe\u63a5ID\u53ef\u552f\u4e00\u6807\u8bc6\u7236\u8282\u70b9\u8868\u793a\u7684\u524d\u7f00\uff0c\u7236\u524d\u7f00\u7edf\u8ba1\u6570\u76ee\u5b58\u50a8\u5728 $$\\textbf{\\scriptsize num[\u5b50\u94fe\u63a5ID]}$$\u82e5\u4ee5\u7236\u8282\u70b9\u6240\u5728\u884c\u6570\u4f5c\u4e3a\u6807\u8bc6\uff0c\u52190\u884c\u65e0\u6cd5\u533a\u5206\u5404\u5355\u5b57\u7b26\u524d\u7f00\u6570\u76ee<\/p>\n
\nconst int MAX_NUM = 10000;\nconst int CHAR_NUM = 26;\nint Trie[MAX_NUM][CHAR_NUM];\nint num[MAX_NUM];\nint rowNum = 0;\n<\/pre>\n
\u8fed\u4ee3\u5b58\u50a8\u7edf\u8ba1\u524d\u7f00\u6570\u76ee<\/h4>\n
void put(string s)\n{\n    int childRowNum = 0;\n    for (int i = 0; s[i]; i++)\n    {\n        int ch = s[i] - 'a';\n        if (Trie[childRowNum][ch] == 0)\n            Trie[childRowNum][ch] = ++rowNum;\n        childRowNum = Trie[childRowNum][ch];\n        num[childRowNum]++;\n    }\n}\n<\/code><\/pre>\n
\u8fed\u4ee3\u5339\u914d\u524d\u7f00\u6570<\/h4>\n
int get(string s)\n{\n    int childRowNum = 0;\n    for (int i = 0; s[i]; i++)\n    {\n        int ch = s[i] - 'a';\n        childRowNum = Trie[childRowNum][ch];\n        if (childRowNum == 0) return 0;\n    }\n    return num[childRowNum];\n}\n<\/code><\/pre>\n
\u6734\u7d20\u5b57\u5178\u5e8f\u4ee3\u7801\u8865\u5168\u5b9e\u73b0<\/h2>\n
\u539f\u7406\u5b9e\u9645\u662f\u5339\u914d\u524d\u7f00\u7684\u6240\u6709\u5b57\u7b26\u4e32\uff0c\u5148\u5e8f\u904d\u5386Trie\u6811\u53ef\u5b9e\u73b0\u5b57\u5178\u5e8f<\/p>\n
(\u5f85\u7eed<\/p>\n
\u6734\u7d20\u8bcd\u9891\u5e8f\u641c\u7d22\u63d0\u793a\u5b9e\u73b0<\/h2>\n
(\u5f85\u7eed<\/p>\n","protected":false},"excerpt":{"rendered":"
Trie \u524d\u7f00\u6811\u662f\u4e00\u4e2aN\u53c9\u6811 \u5b57\u7b26\u4e32\u95f4\u76f8\u540c\u524d\u7f00\u662f\u540c\u4e00\u8def\u5f84 \u7528\u4e8e\u9884\u6d4b\u5b57\u7b26\u4e32\u3001\u5b57\u7b26\u4e32\u5b58\u53d6\u3001\u62fc\u5199\u68c0\u67e5\u548c\u8bcd\u9891\u7edf\u8ba1\u7b49 \u7c7b … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cTrie\u6811 – \u4ee3\u7801\u8865\u5168\u548c\u641c\u7d22\u63d0\u793a\u5b9e\u73b0\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[12],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/1386"}],"collection":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1386"}],"version-history":[{"count":29,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/1386\/revisions"}],"predecessor-version":[{"id":1602,"href":"http:\/\/139.196.114.170\/index.php?rest_route=\/wp\/v2\/posts\/1386\/revisions\/1602"}],"wp:attachment":[{"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1386"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1386"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/139.196.114.170\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1386"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}