将 Unique 元素插入到 trie 中

Question

void insert(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

所以我要插入字符串来创建一个唯一的 trie 数据结构，但是这个插入算法无法检测到任何重复的字符串，有人能帮我看看这个插入算法是如何只用于插入唯一元素的吗？

Answer 1

您可以使用 end 属性或 struct node 检查字符串重复项。让我们调用 find 这个布尔方法并将其添加为 insert 方法的第一行。

bool find(struct node *root, string s)
{
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            return false;
        temp = temp->idx[s[i]-'a'];
    }
    return temp->end;
}

void insert(struct node *root, string s)
{
    if(!find(root, s)) return;
    struct node *temp = root;
    for(int i=0;i<s.length();i++)
    {
        if(temp->idx[s[i]-'a']==NULL)
            temp->idx[s[i]-'a']=create();
        temp = temp->idx[s[i]-'a'];
        (temp->cnt)++;
    }
    temp->end=1;
}

运行时：与之前相同 O(m) 其中 m 是 s 的长度。

注意：我制作了 find 方法，因为无论如何您最多需要遍历 trie 路径的两倍。一种方法是开头提到的，第二种方法是检查重复项 (end 属性) 当你有代表 s 的节点并且如果它确实是重复的字符串那么你再次遍历 s 路径修复 cnt 属性.

中的额外 +1

将 Unique 元素插入到 trie 中

Insert Unique element into trie

trie