Το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg eBay Facebook Google Microsoft
κορδόνι Δέντρο Τρι

Στο Το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie πρόβλημα που έχουμε δώσει ένα σύνολο χορδές, βρείτε το μεγαλύτερο κοινό πρόθεμα. δηλαδή βρείτε το πρόθεμα που είναι κοινό σε όλες τις χορδές.

Παράδειγμα

Input1: {“tutorialcup”, “tutorial”, “tussle”, “tumble”}
Output: "tu"

Input2: {"baggage", "banana", "batsmen"}
Output: "ba"

Input3: {"abcd"}
Output: "abcd"

Input4: {"customer","custard"}
Output: "cust"

Προσέγγιση για το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie

Η ιδέα είναι να χρησιμοποιήσετε μια δομή δεδομένων trie, να εισαγάγετε όλες τις δεδομένες συμβολοσειρές σε αυτήν, να διασχίσετε το trie και να αναζητήσετε τη μεγαλύτερη διαδρομή στο trie χωρίς διακλάδωση. Οι χαρακτήρες που λαμβάνονται κατά μήκος αυτής της διαδρομής είναι οι απαιτούμενοι μας το μεγαλύτερο κοινό πρόθεμα.

Αλγόριθμος για το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie

  1. Κατασκευάστε ένα trie και εισαγάγετε όλες τις συμβολοσειρές εισόδου στο trie. εισάγετε() Η συνάρτηση χρησιμοποιείται για την εισαγωγή μιας μεμονωμένης συμβολοσειράς από τη δεδομένη σειρά συμβολοσειρών ενώ Κατασκευή Trie () χρησιμοποιείται για την εισαγωγή όλων των συμβολοσειρών εισόδου επαναλαμβανόμενα.
  2. αποθηκεύστε το μεγαλύτερο κοινό πρόθεμα στο πρόθεμα μεταβλητός.
  3. Τώρα, ξεκινήστε μια διασταύρωση από τον ριζικό κόμβο του trie και κάντε τα εξής:
    1. ελέγξτε αν ο κόμβος έχει μονό παιδί ή όχι. Δεν έχει παιδί ή περισσότερα από ένα παιδιά, τερματίζει τη διέλευση. Η μέτρηση του αριθμού των μη μηδενικών παιδιών ενός τριπλού κόμβου γίνεται χρησιμοποιώντας λειτουργία countChildren ().
    2. Εάν ο κόμβος έχει ένα μόνο παιδί, προχωρήστε σε αυτό το παιδί και προσθέστε χαρακτήρα που αντιστοιχεί σε αυτόν τον κόμβο στο πρόθεμα.
    3. επαναλάβετε τα βήματα 1 και 2 έως ότου βρεθεί ένας κόμβος χωρίς παιδί (ή περισσότερα από ένα παιδιά) or φτάνουμε σε έναν κόμβο trie που αποθηκεύει τον τελευταίο χαρακτήρα της συντομότερης συμβολοσειράς στη σειρά συμβολοσειρών. Κατά τη διάρκεια κάθε βήματος της διασταύρωσης, συνεχίστε να προσθέτετε χαρακτήρα που αντιστοιχεί σε κάθε τριπλό κόμβο που διέρχεται.
  4. Η διασταύρωση που περιγράφεται στο βήμα 3 υλοποιείται χρησιμοποιώντας τη συνάρτηση walkTrie (), αυτή η συνάρτηση διασχίζει το tri και αναζητά τη μεγαλύτερη κοινή διαδρομή προθέματος και επιστρέφει το αντίστοιχο μακρύτερο κοινό πρόθεμα
  5. Στο τέλος, χρησιμοποιούμε μια λειτουργία προγράμματος οδήγησης μακρύτεροCommonPrefix () που συνδυάζει όλες τις συναρτήσεις που αναφέρονται παραπάνω και επιστρέφει το μακρύτερο κοινό πρόθεμα μεταξύ της δεδομένης σειράς συμβολοσειρών.

 

Το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie

Πρόγραμμα C ++ για το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* structure of a trie Node */
class TrieNode
{
    public:
    TrieNode *child[26];
    bool isEnd;
    
    TrieNode()
    {
        for(int i=0;i<26;i++)
        child[i] = NULL;
        
        isEnd = false;
    }
};

/* inserts a single string into a trie rooted at 'root' */
void insert(TrieNode *root, string key)
{
    TrieNode *temp = root;
    
    for(int i=0;i<key.length();i++)
    {
        int index = int(key[i] - 'a');
        
        if(temp->child[index] == NULL)
        temp->child[index] = new TrieNode();
        
        temp = temp->child[index];
    }
    
    temp->isEnd = true;
}

/* inserts an array of strings into the trie rooted at 'root' */
void constructTrie(TrieNode *root,vector <string> arr)
{
    for(int i=0;i<arr.size();i++)
    insert(root,arr[i]);
}

/* counts number of non NULL children a Trie Node has */
int countChildren(TrieNode *root,int &index)
{
    int count = 0;
    for(int i=0;i<26;i++)
    {
        if(root->child[i] != NULL)
        {
            count++;
            index = i;
        }
    }
    
    return count;
}

/* performs traversal on trie of strings rooted at 'root'
and returns the longest common prefix string */
string walkTrie(TrieNode *root)
{
    TrieNode *temp = root; 
    int index; 
    string prefix; 
  
    while (countChildren(temp, index) == 1 && temp->isEnd == false) 
    { 
        temp = temp->child[index]; 
        prefix.push_back('a'+index); 
    } 
    
    return prefix;
}

/* combines all the function above and return 
LCP among given array of strings */
string longestCommonPrefix(vector <string> arr)
{
    TrieNode *root = new TrieNode();
    constructTrie(root,arr);
    
    string prefix = walkTrie(root);
    
    return prefix;
}


int main()
{
    vector <string> arr = {"tutorialcup", "tutorial", "tussle", "tumble"};
    string ans = longestCommonPrefix(arr);
    
    if(ans.length())
    cout<<"Longest common prefix = "<<ans<<endl;
    else
    cout<<"No common prefix found"<<endl;
    
    return 0;
}
Longest common prefix = tu

Πρόγραμμα Java για το μεγαλύτερο κοινό πρόθεμα χρησιμοποιώντας το Trie

import java.io.*;
import java.util.*;

class tutorialCup
{
    /* structure of a trie Node */
    static class TrieNode
    {
        TrieNode[] child = new TrieNode[26];
        boolean isEnd;
        
        public TrieNode()
        {
            for(int i=0;i<26;i++)
            child[i] = null;
            
            isEnd = false;
        }
    };
    
    /* inserts a single string into a trie rooted at 'root' */
    static void insert(TrieNode root, String key)
    {
        TrieNode temp = root;
        
        for(int i=0;i<key.length();i++)
        {
            int index = key.charAt(i) - 'a';
            
            if(temp.child[index] == null)
            temp.child[index] = new TrieNode();
            
            temp = temp.child[index];
        }
        
        temp.isEnd = true;
    }
    
    /* inserts an array of strings into the trie rooted at 'root' */
    static void constructTrie(TrieNode root,ArrayList <String> arr)
    {
        for(int i=0;i<arr.size();i++)
        insert(root,arr.get(i));
    }
    
    static int index;
    
    /* counts number of non NULL children a Trie Node has */
    static int countChildren(TrieNode root)
    {
        int count = 0;
        for(int i=0;i<26;i++)
        {
            if(root.child[i] != null)
            {
                count++;
                index = i;
            }
        }
        
        return count;
    }
    
    /* performs traversal on trie of strings rooted at 'root'
    and returns the longest common prefix string */
    static StringBuffer walkTrie(TrieNode root)
    {
        TrieNode temp = root; 
        StringBuffer prefix = new StringBuffer(); 
      
        while (countChildren(temp) == 1 && temp.isEnd == false) 
        { 
            temp = temp.child[index]; 
            prefix.append((char)('a'+index)); 
        } 
        
        return prefix;
    }
    
    /* combines all the function above and return 
    LCP among given array of strings */
    static StringBuffer longestCommonPrefix(ArrayList <String> arr)
    {
        TrieNode root = new TrieNode();
        constructTrie(root,arr);
        
        StringBuffer prefix = walkTrie(root);
        
        return prefix;
    }
    
    public static void main (String[] args) 
    {
        ArrayList <String> arr = new ArrayList<>(Arrays.asList("tutorialcup", "tutorial", "tussle", "tumble"));
        StringBuffer ans = longestCommonPrefix(arr);
        
        if(ans.length() != 0)
        System.out.print("Longest common prefix = "+ans);
        else
        System.out.print("No common prefix found");
        
    }
}
Longest common prefix = tu

Ανάλυση πολυπλοκότητας

  1. Πολυπλοκότητα χρόνου: T (n) = O (mn), άνω όριο του χρόνου που απαιτείται κατασκευάσει η τρι.
  2. Διαστημική πολυπλοκότητα: A (n) = O (mn), άνω όριο του χώρου που καταλαμβάνει η trie στη μνήμη.

όπου,

n = μήκος της μεγαλύτερης συμβολοσειράς

m = αριθμός συμβολοσειρών στον πίνακα συμβολοσειρών.

αναφορές