Рубрики

Соответствие самого длинного префикса — решение на основе Trie в Java

По словарю слов и входной строке найдите самый длинный префикс строки, который также является словом в словаре.

Примеры:

Let the dictionary contains the following words:
{are, area, base, cat, cater, children, basement}

Below are some input/output examples:
--------------------------------------
Input String            Output
--------------------------------------
caterer                 cater
basemexy                base
child                   < Empty >

Решение
Мы строим Trie из всех словарных слов. Как только Trie будет построен, пройдите через него, используя символы входной строки. Если префикс соответствует словарному слову, сохраните текущую длину и найдите более длинное соответствие. Наконец, верните самый длинный матч.
Ниже приведена реализация вышеупомянутого решения на Java.

import java.util.HashMap;

  
// Trie Node, который хранит персонажа и детей в HashMap

class TrieNode {

    public TrieNode(char ch)  {

        value = ch;

        children = new HashMap<>();

        bIsEnd = false;

    }

    public HashMap<Character,TrieNode> getChildren() {   return children;  }

    public char getValue()                           {   return value;     }

    public void setIsEnd(boolean val)                {   bIsEnd = val;     }

    public boolean isEnd()                           {   return bIsEnd;    }

  

    private char value;

    private HashMap<Character,TrieNode> children;

    private boolean bIsEnd;

}

  
// Реализует фактический Trie

class Trie {

    // Конструктор

    public Trie()   {     root = new TrieNode((char)0);       }    

  

    // Метод для вставки нового слова в Trie

    public void insert(String word)  {

  

        // Найти длину заданного слова

        int length = word.length();

        TrieNode crawl = root;

  

        // Пройти через все символы данного слова

        for( int level = 0; level < length; level++)

        {

            HashMap<Character,TrieNode> child = crawl.getChildren();

            char ch = word.charAt(level);

  

            // Если для текущего символа заданного слова уже есть дочерний элемент

            if( child.containsKey(ch))

                crawl = child.get(ch);

            else   // Остальное создадим ребенка

            {

                TrieNode temp = new TrieNode(ch);

                child.put( ch, temp );

                crawl = temp;

            }

        }

  

        // Установить bIsEnd true для последнего символа

        crawl.setIsEnd(true);

    }

  

    // Основной метод, который находит самую длинную строку 'input'

    public String getMatchingPrefix(String input)  {

        String result = ""; // Инициализировать результирующую строку

        int length = input.length();  // Находим длину входной строки

  

        // Инициализируем ссылку для прохождения через Trie

        TrieNode crawl = root;   

  

        // Перебираем все символы входной строки 'str' и перемещаемся

        // вниз по дереву

        int level, prevMatch = 0;

        for( level = 0 ; level < length; level++ )

        {

            // Найти текущий символ str

            char ch = input.charAt(level);    

  

            // HashMap текущего узла Trie для перехода вниз

            HashMap<Character,TrieNode> child = crawl.getChildren();                        

  

            // Посмотрим, есть ли край Trie для текущего символа

            if( child.containsKey(ch) )

            {

               result += ch;          // Обновить результат

               crawl = child.get(ch); // Обновление сканирования для перемещения вниз в Trie

  

               // Если это конец слова, то обновляем prevMatch

               if( crawl.isEnd() )

                    prevMatch = level + 1;

            }

            else  break;

        }

  

        // Если последний обработанный символ не соответствует концу слова,

        // возвращаем ранее соответствующий префикс

        if( !crawl.isEnd() )

                return result.substring(0, prevMatch);        

  

        else return result;

    }

  

    private TrieNode root;

}

  
// Тестовый класс

public class Test {

   public static void main(String[] args) {

        Trie dict = new Trie();

        dict.insert("are");

        dict.insert("area");

        dict.insert("base");

        dict.insert("cat");

        dict.insert("cater");

        dict.insert("basement");

  

        String input = "caterer";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));              

  

        input = "basement";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));                      

  

        input = "are";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));              

  

        input = "arex";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));              

  

        input = "basemexz";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));                      

  

        input = "xyz";

        System.out.print(input + ":   ");

        System.out.println(dict.getMatchingPrefix(input));

    }

}

Выход:

caterer:   cater
basement:   basement
are:   are
arex:   are
basemexz:   base
xyz:   

Сложность по времени: сложность по времени при нахождении самого длинного префикса составляет O (n), где n — длина входной строки. Обратитесь к этому для временной сложности построения Trie.

Эта статья составлена Рави Чандрой Энаганти . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Соответствие самого длинного префикса — решение на основе Trie в Java

0.00 (0%) 0 votes