DFS по сравнению со строкой (префикс)

Итак, сначала нам нужно уточнить, что наиболее длинный общий префикс здесь означает самый длинный общий префикс любых двух или более строк в дереве дерева.

Таким образом, ваш метод поиска в глубину не будет работать, потому что он просто обходит все дерево и выводит "найдена первая вершина" при посещении любого узла, у которого children.size() > 2 (это здесь должно быть >=2)

Здесь нам нужно найти только самый длинный общий префикс. Поэтому нам нужна дополнительная информация о том, какой из них самый длинный. Это легко увидеть в моем примере выше:

          root      --depth: 0
           |
           a        --depth: 1
           |
           b        --depth: 2
          / \
         c   f      --depth: 3
        /|\
       d g k        --depth: 4
            \
             k      --depth: 5 

Самый длинный общий узел префикса имеет children.size()>1 AND максимальную глубину. В данном случае это узел c

Итак, вот один из возможных правильных DFS:

static int max=-1;
static TrieNode maxNode=null;

static void dfs(TrieNode node, int depth){
    if(node.children.size()>1 && depth>max){
        max=depth;
        maxNode=node;
    }
    for (TrieNode tn: node.children.values())
        dfs(tn,depth+1);
}

public static void test(){
    TrieNode root = Tree.createTree();
    Tree.insertWord(root, "abcd");
    Tree.insertWord(root, "abcg");
    Tree.insertWord(root, "abckk");
    Tree.insertWord(root, "abf");
    dfs(root,0);
    System.out.println("Max node:"+maxNode.letter);
}

После запуска dfs maxNode будет содержать узел, на котором останавливается самый длинный общий префикс. в данном случае это узел c.

Ваш код дерева префиксов кажется хорошим. По крайней мере, для меня это имеет смысл, но я не проверял все крайние случаи. Проблема в вашем методе DFS. Предполагая, что у нас есть следующие строки, которые состоят из вашего дерева префиксов:

- "abcd"
- "abcg"
- "abckk"
- "abf"

Итак, дерево префиксов должно выглядеть так:

              root
               |
               a
               |
               b
              / \
             c   f
            /|\
           d g k
                \
                 k

Я думаю, вы ожидаете, что мы сможем вывести "найдена первая вершина" в узле b (потому что, очевидно, "ab" является самым длинным общим префиксом вершины). над четырьмя строками), однако ваша DFS не работает таким образом. Он пойдет по пути

root->a->b->c->d then back to c, finding that c.children.size() >1 , then output.

Обратите внимание, что "2 или больше" – это >=2 или >1, что в вашей программе равно >2. Я подумал, что это опечатка. Чтобы исправить DFS, просто измените его, чтобы сначала проверить размер дочернего узла:

static boolean DFS(TrieNode node) {
    if (node.children.size()>1){
        System.out.println("found the first vertex on node:"+node.letter);
        return true;
    }
    for (TrieNode tn: node.children.values()){
        if(DFS(tn))
            return true;
    }
    return false;
}

Обратите внимание, чтобы программа остановилась при поиске нашего узла, я изменяю тип возвращаемого вами DFS. Кроме того, что касается поиска самого длинного общего префикса, DFS здесь может быть не лучшим выбором, следующий код лучше, чем DFS, с точки зрения сложности выполнения:

static void lcp(TrieNode node){
    TrieNode first = node;
    while(first.children.size()==1)
        first = first.children.values().iterator().next();
    System.out.println("found the first vertex on node:"+first.letter);
}