Как получить длину самого длинного префикса в три в C - PullRequest
Новая
       29

Как получить длину самого длинного префикса в три в C

0 голосов
/ 18 октября 2018

Я пытаюсь выяснить, как найти длину самого длинного префикса двух слов в три.Я пытался найти решение, но ничего не нашел.

У меня уже есть реализация 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;
    }
...