c - 如何在C中获取Trie中最长前缀的长度

Question

我试图弄清楚如何在 Trie 中找到两个单词的最长前缀的长度。我试图找到解决方案，但我什么也没找到。

我已经有一个 Trie 的实现，其中节点由结构表示：

struct node
{
    int end;    // 1 if node is end of word or 0 if not
    int count;  // The number of words that contain current node
    struct node *letter[26]; // Array of nodes, which represent the alphabet
};

int length_of_longest_prefix(struct node *root)
{
   //??????????
}

我试图为这个问题创建一个递归函数，但我做不到。

让我们想想这个填充特里： 填充特里

解决这个问题的最佳方法是什么？伪代码将非常有用。

我的功能：

//Global variable
  int total_max;

//root = start
int length_of_longest_prefix(struct node *root, struct node *start)
{
    int max = 0;
    int depth = 0;

    for (int i = 0; i < 26; i++)
    {
        if(root->letter[i] != NULL && root->letter[i]->count >= 2)
        {
            depth = length_of_longest_prefix(root->letter[i], start);
            depth++;

            if(root->letter[i] == start->letter[i])
            {
                depth = 0;
            }
        }

        if(depth > total_max)
            total_max = depth;
    }
        return depth;
}

    int main(void)
    {
     total_max = 0;
     struct node *root = (struct node*)malloc(sizeof(struct node));

     for (int i = 0; i < 26; i++)
     {
        root->letter[i] = NULL;
     }

     root->end = 0;
     root->count = 0;

    /*Inserting strings to Trie*/

     length_of_longest_prefix(root, root);
     printf("%d\n", total_max);

     return 0;
    }

标签： cpseudocodeprefixtrie