longest common prefix algo



  • Hello,

    welche datenstruktur eignet sich am besten für folgenden algo?

    Write a function to find the longest common prefix string amongst an array of strings.

    Ansatz: trie, welcher alle strings darin abspeichert...
    der knoten (davon gibt es 26, wenn ich 'a' bis 'z' nehme) im trie hat einen counter, d.h. wenn 2 strings sich überlappen, dann wäre der counter >= 2...

    fällt ich noch eine bessere, mehr effizientere lösung ein?



  • bejan schrieb:

    Hello,
    welche datenstruktur eignet sich am besten für folgenden algo?

    Ansatz: trie, welcher alle strings darin abspeichert...

    Ähm, gar keine. Brauchst doch nur den ersten String und die bisherige gemeinsame Länge. Und dann immer den näcnsten mit dem ersten vergleichen und wenn die gemeinsame Länge kürzer ist, sie updaten.



  • ich dazu nicht folgendes erwaehnt:
    Find Longest Common Prefix from N strings...also nicht nur 2 🙂



  • template< typename I >
    std::string longest_common_prefix( I from, I to )
    {
        if( from == to )
            return std::string();
        I cur = from;
        std::string::size_type n = cur->length();   // Brauchst doch nur den ersten String ...
        for( ++cur; cur != to; ++cur )  // Und dann immer ..
        {
            std::string::size_type n2 = 0;
            for( auto i = begin(*from), j = begin(*cur) // .. den näcnsten mit dem ersten vergleichen .
                ; n2 < n && j != end(*cur) && *i == *j; ++i, ++j )
                ++n2;
            if( n2 < n )    // .. und wenn die gemeinsame Länge kürzer ist, ..
                n = n2;     // .. sie updaten
        }
        return std::string( begin(*from), begin(*from)+n );
    }
    
    int main()
    {
        using namespace std;
        string texte[] = {
            string("das ist der erste"),
            string("das ist doof"),
            string("dahinter steckt nix"),
            string("das ist alles"),
        };
        cout << "longest_common_prefix = '" << longest_common_prefix(begin(texte), end(texte)) << "'" << endl;
    }
    


  • folgender input gibt nicht den longest common prefix zurueck:

    string texte[] = { 
            string("das ist der erste"), 
            string("das ist doof"), 
            string("bello"), 
            string("dahinter steckt nix"), 
            string("das ist alles"), 
            string("bella"), 
        };
    


  • So so !?



  • bejan schrieb:

    folgender input gibt nicht den longest common prefix zurueck:

    string texte[] = { 
            string("das ist der erste"), 
            string("das ist doof"), 
            string("bello"), 
            string("dahinter steckt nix"), 
            string("das ist alles"), 
            string("bella"), 
        };
    

    Da liegt dann ein Mißverständnis vor. Was wäre denn Deiner Meinung nach der longest prefix? Ach, Du meinst 'das ist ' (sogar mit Häufigkeit 3).
    Klar, dann brauchts bessere Datenstrukturen oder Algos. Präfixbaum&Co oder vielleicht besser mal vorher sortieren und den hier gezeigten Code ganz ein bißchen anpassen, halt Nachbarn vergleichen, *cur mit *(cur-1) vielleicht.



  • @volkard sorry missverständnis, fuer longest COMMON prefix ist der algo zuvor richtig!

    anbei meine loesung: im moment nur für wörter bestehend aus 'a' - 'z'
    verbraucht etwas speicher fuer den trie...
    stimmen die laufzeit berechnung fuer die 2 funktionen?
    wie schnell laueft dein algo Kenner von volkard?

    #include <iostream>
    #include <vector>
    using namespace std;
    
    const int alphabet_size = 26;
    
    class Node {
    public:
      Node *next[alphabet_size];
      bool isEnd;
      int count;
    
    public:
      Node(): isEnd(false), count(0) {}
    };
    
    class trie {
    private:
      Node *root;
      int wordsCount;
    
    public:
      trie() {
      	wordsCount = 0;
        root = createNode();
      }
    
      Node *createNode() {
        Node *n = new Node;
    
        for (int i = 0; i < alphabet_size; i++) {
          n->next[i] = NULL;
        }
    
        return n;
      }
    
      // O(26 * n) ... n = length of the string to insert
      void insert(const string &str) {
        Node *tmp = root;
    
        for (int i = 0; i < str.size(); i++) {
          char k = str[i] - 'a';
    
          if (!tmp->next[k]) {
            tmp->next[k] = createNode();
          } 
    
          tmp->isEnd = false;
          tmp->count++;
    	  tmp = tmp->next[k];
        }
    
        tmp->isEnd = true;
        wordsCount++;
      }
    
      // O(26 * m) ... m = length of the longest common prefix
      string findLongestCommonPrefix() {
      	Node *tmp = root;
      	string prefix;
    
      	while(true) {
      		bool found = false;
      		int storeIndex = 0;
    
      		for (int i = 0; i < alphabet_size; i++) {
      			if (tmp->next[i] && 
      			    tmp->next[i]->count == wordsCount) {
      				storeIndex = i;
      				found = true;
      			}
      		}
    
      		if (found) {
      			prefix += static_cast<char>(storeIndex + 'a');
      			tmp = tmp->next[storeIndex];
      		}
      		else {
      			break;
      		}
      	}
    
      	return prefix;
      }
    };
    
    int main() {
      // your code goes here
    
      trie t;
    
      vector<string> text = { 
        {"dasistdererste"}, 
        {"dasistdoof"}, 
        {"dahinterstecktnix"}, 
        {"dasistalles"}
      };
    
      for (int i = 0; i < text.size(); i++) {  
      	t.insert(text[i]);
      }
    
      cout << t.findLongestCommonPrefix() << endl;
    
      return 0;
    }
    


  • bejan schrieb:

    anbei meine loesung: im moment nur für wörter bestehend aus 'a' - 'z'
    verbraucht etwas speicher fuer den trie...
    stimmen die laufzeit berechnung fuer die 2 funktionen?
    wie schnell laueft dein algo Kenner von volkard?

    Rechne mal mit 100 Takten pro new/delete.
    Wird also knapp, ob Du erst zwei oder schon drei Buchstaben drin hast, wo der Kvv schon fertig ist.



  • bejan schrieb:

    wie schnell laueft dein algo Kenner von volkard?

    ca. Faktor 14 schneller:

    bejan: longest_common_prefix = 'da' in 0.0137943ms
    Kenner: longest_common_prefix = 'da' in 0.000962391ms



  • bejan schrieb:

    stimmen die laufzeit berechnung fuer die 2 funktionen?

    Bei der O-Notation kannste konstante Faktoren weglassen.
    Also O(n) schreiben, wenn Du O(26*n) berechnet hattest.

    Bei der ersten sehe ich auch nicht, wie Du aufs 26* kommst. Höchstens in der Annahme, daß das Array next korrekt mit Nullzeigern initialisiert werden würde, aber mir scheint, darauf haste großzügig verzichtet.



  • @volkard: for inserting a word of length 'k' we need (k * 26) comparisons...



  • bejan schrieb:

    @volkard: for inserting a word of length 'k' we need (k * 26) comparisons...

    Zieh alphabet_size mal hoch auf 256. Hmm, das ist aber unhünsch viel verschwendeter Speicher. Wie machen wir denn das? Vielleicht als vector<pair<char,Node*>> und pushen neue Buchstaben rein und suchen Buchstaben mit einer for-Schleife? Ja, das riecht nach k*26.



  • @volkard: ja das new dürste alles relativ langsam machen...

    @Kenner von volkard: und wie berechnest du deine Laufzeitkomplexität O(...)?


Log in to reply