longest common prefix algo

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 !?

volkard

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;
}

volkard

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

volkard

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...

volkard

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(...)?