longest contiguous common substring



  • hi,

    wie kann ich den longest contiguous common substring finden?

    angenommen ich habe 2 strings:
    str1 = "helloworld"
    str2 = "bellaworldcup"

    dann gaebe es da zwei laengesten common substrings: "ell" und "world":

    wie erstelle ich den suffix tree dafuer?

    muss ich da die folgenden strings in den suffix tree einfuegen?
    "helloworld"
    "helloworl"
    "hellowor"
    "hellowo"
    "hellow"
    "hello"
    "hell"
    "hel"
    "he"
    "h"
    "elloworld"
    "lloworld"
    "loworld"
    "oworld"
    "world"
    "orld"
    "rld"
    "ld"
    "d"

    und kann danach nach einem substring in str2 suchen?
    "bellaworldcup"
    "ellaworld" <--- substring "ell" found
    "llaworld"
    "laworld"
    "aworld"
    "world" <--- substring "world" found --> is longest common substring
    "orld"
    "rld"
    "ld"
    "d"

    welche komplexitaet hat das einfuegen der substrings in den suffix tree?

    trie<char> t;
    for(int i = 0; i < str1.size(); i++) {
    	t.put(str1.substr(i, str1.size() - i), 1); // "elloworld"
            t.put(str1.substr(0, str1.size() - i), 1); // "helloworl"
    }
    

    insert in suffix tree oder trie ist ja O(k) ... k = alphabet size ?
    string::substr .. O(n) ... n = number of chars ?



  • ich muss nur folgende suffixes in den tree einfuegen:

    "helloworld" 
    "elloworld" 
    "lloworld" 
    "loworld" 
    "oworld" 
    "world" 
    "orld" 
    "rld" 
    "ld" 
    "d"
    

    insert in den trie/suffix tree waere dann folgender code:

    trie<char> t;
    for(int i = 0; i < str1.size(); i++) {
        t.put(str1.substr(i, str1.size() - i), 1); // "elloworld"
    }
    

    komplexitaet waere dann folgende?
    O(n * (n + k)) = O(n^2 + k) ?



  • Hallo,

    unter Longest common substring problem findest du alle benötigten Infos.
    Die dynamische Programmierung findest z.B. auch bei Levenshtein-Distanz Anwendung (falls du nicht auf Anhieb verstanden hast, wie dynamische Programmierung funktioniert).



  • Hi, die frage hat sich auf die implementierung mit einem suffix tree bezogen!

    Ist die berechnete komplexitaet korrekt?



  • Jeff1 schrieb:

    Ist die berechnete komplexitaet korrekt?

    Bis auf die Umformung sieht sie korrekt aus (O(n*(n+k))=O(n2+n*k)).

    Ein Trick in der Implementierung wäre, t.put(str1.c_str()+i, 1) aufzurufen (und im trie const char* entgegennehmen), das erspart dir eine unnötige Kopie. Ändert aber nichts an der Komplexität.

    Eine speicherschonendere Art, einen trie zu implementieren, ist, alles in einen vector<const char*> einzufügen und zu sortieren (Radix sort), damit hat man aber immer noch die gleiche Laufzeitkomplexität, dafür nur O(n) Speicher.


Log in to reply