字典樹是一種能夠快速插入和查詢字符串的多叉樹結(jié)構(gòu)，節(jié)點的編號各不相同，根節(jié)點編號為0

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。

核心思想也是通過空間來換取時間上的效率

在一定情況下字典樹的效率要比哈希表要高

字典樹在解決公共前綴的使用，所以叫前綴樹

?先說如何創(chuàng)建字典樹

這個是只有26個小寫字母存放的字典樹

class TrieNode{
public:
    TrieNode* next[26];
    bool isword;
    TrieNode(){
        memset(next,NULL,sizeof(next));
        isword=false;
    }
    ~TrieNode(){
        for(int i=0;i<26;i++)if(next[i])delete next[i];
    }
};

也可以直接用c++中的特殊的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)

struct Node {
    unordered_map<int, Node*> son;
    int cnt = 0;
};

但是在下面必須要對根節(jié)點進行補充，根節(jié)點為空

Node *root = new Node();

leetcode3043. 最長公共前綴的長度-CSDN博客

leetcode3042. 統(tǒng)計前后綴下標對 I-CSDN博客

力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術(shù)成長平臺

這道題之前用的暴力去模擬這個過程,效率太低,，采用前綴樹來解決

class Solution {
public:

    long long countPrefixSuffixPairs(vector<string>& words) {
        long long cnt=0;
        int i,j;
        for(i=0;i<words.size()-1;i++){
            for(j=i+1;j<words.size();j++){
                       if(words[j].find(words[i])==0 && words[j].rfind(words[i])==words[j].length()-words[i].length()){
                           cnt++;
                       }
            }
        }
        return cnt;
    }
};

但是前綴樹解決的是前綴的問題，這道題讓解決的是前綴和后綴的問題，所以想要把這個字符串轉(zhuǎn)變一下來解決，

【1】首先我先到的是建造兩個前綴樹，一個正向前綴樹，一個反向前綴樹

?【2】可以用一個pair去儲存步驟1的過程

正 ab? ? ? ? ? ? ? ? ? ?abcdab

反 ba? ? ? ? ? ? ? ? ? ?badcba

[(a,b),(b,a)]? ? ? ? ? ? ?[(a,b),(b,a),.....]

由此可見如果是前后綴的話，應(yīng)該會在pair列表中出現(xiàn)文章來源地址http://www.zghlxwxcb.cn/news/detail-833726.html

class Node:
    __slots__ = 'son', 'cnt'

    def __init__(self):
        self.son = dict()
        self.cnt = 0

class Solution:
    def countPrefixSuffixPairs(self, words: List[str]) -> int:
        ans = 0
        root = Node()
        for t in words:
            z = self.calc_z(t)
            cur = root
            for i, c in enumerate(t):
                if c not in cur.son:
                    cur.son[c] = Node()
                cur = cur.son[c]
                if z[-1 - i] == i + 1:  # t[-1-i:] == t[:i+1]
                    ans += cur.cnt
            cur.cnt += 1
        return ans

    def calc_z(self, s: str) -> List[int]:
        n = len(s)
        z = [0] * n
        l, r = 0, 0
        for i in range(1, n):
            if i <= r:
                z[i] = min(z[i - l], r - i + 1)
            while i + z[i] < n and s[z[i]] == s[i + z[i]]:
                l, r = i, i + z[i]
                z[i] += 1
        z[0] = n
        return z

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)---字典樹（Tire）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！