Рубрики

Самый длинный общий префикс с использованием Trie

Учитывая набор строк, найдите самый длинный общий префикс.

Input  : {“geeksforgeeks”, “geeks”, “geek”, “geezer”}
Output : "gee"

Input  : {"apple", "ape", "april"}
Output : "ap"

Предыдущие подходы: Слово за слово Matching , посимвольно Matching , разделяй и властвуй , бинарный поиск .

В этой статье обсуждается подход с использованием структуры даты Trie .
шаги:

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

    Это потому, что символы (узлы в trie), которые присутствуют в самом длинном общем префиксе, должны быть единственным потомком его родителя, т. Е. Не должно быть ветвления ни в одном из этих узлов.

Иллюстрация алгоритма, рассматривающая строки как — «geeksforgeeks», «geeks», «geek», «geezer»

C ++

// Программа для поиска самых распространенных
// префикс заданных слов

  
#include<bits/stdc++.h>

using namespace std;

  
// Размер алфавита (количество символов)
#define ALPHABET_SIZE (26)

  
// Преобразует текущий символ ключа в индекс
// использовать только буквы от 'a' до 'z' и строчные буквы
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

  
// Три узла

struct TrieNode

{

    struct TrieNode *children[ALPHABET_SIZE];

  

    // isLeaf имеет значение true, если узел представляет

    // конец слова

    bool isLeaf;

};

  
// Возвращает новый три-узел (инициализируется NULL)

struct TrieNode *getNode(void)

{

    struct TrieNode *pNode = new TrieNode;

  

    if (pNode)

    {

        int i;

  

        pNode->isLeaf = false;

  

        for (i = 0; i < ALPHABET_SIZE; i++)

            pNode->children[i] = NULL;

    }

  

    return pNode;

}

  
// Если нет, вставляет ключ в три
// Если ключ является префиксом узла trie, просто помечаем конечный узел

void insert(struct TrieNode *root, string key)

{

    int length = key.length();

    int index;

  

    struct TrieNode *pCrawl = root;

  

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

    {

        index = CHAR_TO_INDEX(key[level]);

        if (!pCrawl->children[index])

            pCrawl->children[index] = getNode();

  

        pCrawl = pCrawl->children[index];

    }

  

    // пометить последний узел как лист

    pCrawl->isLeaf = true;

}

  
// Подсчитывает и возвращает количество потомков
// текущий узел

int countChildren(struct TrieNode *node, int *index)

{

    int count = 0;

    for (int i=0; i<ALPHABET_SIZE; i++)

    {

        if (node->children[i] != NULL)

        {

            count++;

            *index = i;

        }

    }

    return (count);

}

  
// Выполнить прогулку по дереву и вернуть
// самая длинная строка общего префикса

string walkTrie(struct TrieNode *root)

{

    struct TrieNode *pCrawl = root;

    int index;

    string prefix;

  

    while (countChildren(pCrawl, &index) == 1 &&

            pCrawl->isLeaf == false)

    {

        pCrawl = pCrawl->children[index];

        prefix.push_back('a'+index);

    }

    return (prefix);

}

  
// Функция для построения дерева

void constructTrie(string arr[], int n, struct TrieNode *root)

{

    for (int i = 0; i < n; i++)

        insert (root, arr[i]);

    return;

}

  
// Функция, которая возвращает самый длинный общий префикс
// из массива строк

string commonPrefix(string arr[], int n)

{

    struct TrieNode *root = getNode();

    constructTrie(arr, n, root);

  

    // Выполнить прогулку по дереву

    return walkTrie(root);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string arr[] = {"geeksforgeeks", "geeks",

                    "geek", "geezer"};

    int n = sizeof (arr) / sizeof (arr[0]);

  

    string ans = commonPrefix(arr, n);

  

    if (ans.length())

        cout << "The longest common prefix is "

             << ans;

    else

        cout << "There is no common prefix";

    return (0);

}

Джава

// Java-программа для поиска самых распространенных
// префикс заданных слов

public class Longest_common_prefix {

      

    // Размер алфавита (количество символов)

    static final int ALPHABET_SIZE = 26;

       

    // Три узла

    static class TrieNode

    {

        TrieNode[] children = new TrieNode[ALPHABET_SIZE];

       

        // isLeaf имеет значение true, если узел представляет

        // конец слова

        boolean isLeaf;

          

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

        public TrieNode() {

            isLeaf = false;

            for (int i = 0; i < ALPHABET_SIZE; i++)

                children[i] = null;

        }

    };

       

    static TrieNode root;

    static int indexs;

       

    // Если нет, вставляет ключ в три

    // Если ключ является префиксом узла trie, просто помечаем

    // листовой узел

    static void insert(String key)

    {

        int length = key.length();

        int index;

       

        TrieNode pCrawl = root;

       

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

        {

            index = key.charAt(level) - 'a';

            if (pCrawl.children[index] == null)

                pCrawl.children[index] = new TrieNode();

       

            pCrawl = pCrawl.children[index];

        }

       

        // пометить последний узел как лист

        pCrawl.isLeaf = true;

    }

       

    // Подсчитывает и возвращает количество потомков

    // текущий узел

    static int countChildren(TrieNode node)

    {

        int count = 0;

        for (int i=0; i<ALPHABET_SIZE; i++)

        {

            if (node.children[i] != null)

            {

                count++;

                indexs = i;

            }

        }

        return (count);

    }

       

    // Выполнить прогулку по дереву и вернуть

    // самая длинная строка общего префикса

    static String walkTrie()

    {

        TrieNode pCrawl = root;

        indexs = 0;

        String prefix = "";

       

        while (countChildren(pCrawl) == 1 &&

                pCrawl.isLeaf == false)

        {

            pCrawl = pCrawl.children[indexs];

            prefix += (char)('a' + indexs);

        }

        return prefix;

    }

       

    // Функция для построения дерева

    static void constructTrie(String arr[], int n)

    {

        for (int i = 0; i < n; i++)

            insert (arr[i]);

        return;

    }

       

    // Функция, которая возвращает самый длинный общий префикс

    // из массива строк

    static String commonPrefix(String arr[], int n)

    {

        root = new TrieNode();

        constructTrie(arr, n);

       

        // Выполнить прогулку по дереву

        return walkTrie();

    }

       

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        String arr[] = {"geeksforgeeks", "geeks",

                        "geek", "geezer"};

        int n = arr.length;

       

        String ans = commonPrefix(arr, n);

       

        if (ans.length() != 0)

            System.out.println("The longest common prefix is "+ans);

        else

            System.out.println("There is no common prefix");

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Программа Python 3, чтобы найти самый длинный общий префикс

ALPHABET_SIZE = 26

indexs = 0

class TrieNode:

    # конструктор

    def __init__(self):

        self.isLeaf = False

        self.children = [None]*ALPHABET_SIZE

  
# Функция для облегчения вставки в Trie
# Если нет, вставьте узел в Trie

def insert(key, root):

    pCrawl = root

    for level in range(len(key)):

        index = ord(key[level]) - ord('a')

        if pCrawl.children[index] == None:

            pCrawl.children[index] = TrieNode()

        pCrawl = pCrawl.children[index]

    pCrawl.isLeaf = True

  
# Функция для построения Trie

def constructTrie(arr, n, root):

    for i in range(n):

        insert(arr[i], root)

  
# Подсчитывает и возвращает количество дочерних элементов узла

def countChildren(node):

    count = 0

    for i in range(ALPHABET_SIZE):

        if node.children[i] != None:

            count +=1

            # Отслеживание утечки в три

            global indexs

            indexs = i

    return count

      
# Выполнить прогулку по три и вернуть самый длинный общий префикс

def walkTrie(root):

    pCrawl = root

    prefix = ""

    while(countChildren(pCrawl) == 1 and pCrawl.isLeaf == False):

        pCrawl = pCrawl.children[indexs]

        prefix += chr(97 + indexs)

    return prefix or -1

  
# Функция, которая возвращает самый длинный общий префикс

def commonPrefix(arr, n, root):

    constructTrie(arr, n, root)

    return walkTrie(root)

  
# Код драйвера для проверки кода

n = 4

arr = ["geeksforgeeks", "geeks", "geek", "geezer"]

root = TrieNode()

print(commonPrefix(arr,n, root))

  
# Этот код предоставлен Акшаем Джайном (DA-IICT)

C #

// C # Программа для поиска самых распространенных
// префикс заданных слов

using System;

      

public class Longest_common_prefix 

{

      

    // Размер алфавита (количество символов)

    static readonly int ALPHABET_SIZE = 26;

      

    // Три узла

    public class TrieNode

    {

        public TrieNode[] children = new TrieNode[ALPHABET_SIZE];

      

        // isLeaf имеет значение true, если узел представляет

        // конец слова

        public bool isLeaf;

          

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

        public TrieNode() 

        {

            isLeaf = false;

            for (int i = 0; i < ALPHABET_SIZE; i++)

                children[i] = null;

        }

    };

      

    static TrieNode root;

    static int indexs;

      

    // Если нет, вставляет ключ в три

    // Если ключ является префиксом узла trie, просто помечаем

    // листовой узел

    static void insert(String key)

    {

        int length = key.Length;

        int index;

      

        TrieNode pCrawl = root;

      

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

        {

            index = key[level] - 'a';

            if (pCrawl.children[index] == null)

                pCrawl.children[index] = new TrieNode();

      

            pCrawl = pCrawl.children[index];

        }

      

        // пометить последний узел как лист

        pCrawl.isLeaf = true;

    }

      

    // Подсчитывает и возвращает количество потомков

    // текущий узел

    static int countChildren(TrieNode node)

    {

        int count = 0;

        for (int i = 0; i < ALPHABET_SIZE; i++)

        {

            if (node.children[i] != null)

            {

                count++;

                indexs = i;

            }

        }

        return (count);

    }

      

    // Выполнить прогулку по дереву и вернуть

    // самая длинная строка общего префикса

    static String walkTrie()

    {

        TrieNode pCrawl = root;

        indexs = 0;

        String prefix = "";

      

        while (countChildren(pCrawl) == 1 &&

                pCrawl.isLeaf == false)

        {

            pCrawl = pCrawl.children[indexs];

            prefix += (char)('a' + indexs);

        }

        return prefix;

    }

      

    // Функция для построения дерева

    static void constructTrie(String []arr, int n)

    {

        for (int i = 0; i < n; i++)

            insert (arr[i]);

        return;

    }

      

    // Функция, которая возвращает самый длинный общий префикс

    // из массива строк

    static String commonPrefix(String []arr, int n)

    {

        root = new TrieNode();

        constructTrie(arr, n);

      

        // Выполнить прогулку по дереву

        return walkTrie();

    }

      

    // Программа драйвера для проверки вышеуказанной функции

    public static void Main(String []args)

    {

        String []arr = {"geeksforgeeks", "geeks",

                        "geek", "geezer"};

        int n = arr.Length;

      

        String ans = commonPrefix(arr, n);

      

        if (ans.Length != 0)

            Console.WriteLine("The longest common prefix is "+ans);

        else

            Console.WriteLine("There is no common prefix");

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход :

The longest common prefix is gee

Сложность времени: вставка всех слов в три занимает O (MN) времени, а выполнение прогулки по три занимает O (M) времени, где

N = Number of strings
M = Length of the largest string

Вспомогательное пространство: Для хранения всех строк нам нужно выделить O (26 * M * N) ~ O (MN) место для Trie.

Эта статья предоставлена Rachit Belwariar . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Самый длинный общий префикс с использованием Trie

0.00 (0%) 0 votes