longest common prefix algo
-
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(...)?