zeichenkette erkennen und zyklusfolge ausgeben



  • Hallo Leute, ich hoffe ihr könnt mir bei folgender Aufgabe helfen, ich blick da echt nicht mehr durch...

    Schreiben Sie eine Funktion, die prüft, ob eine eingegebene Zeichenkette aus einer zyklischen Aufeinanderfolge einer Teilzeichenkette besteht, gegebenenfalls die (minimale) Zykluslänge bestimmt und an die aufrufende Funktion retourniert z.B.:
    Eingabe: abcabca Ausgabe: Zykluslänge 3
    Eingabe: abcabcd Ausgabe: nicht zyklisch

    danke schon mal im voraus 🙂



  • Wie sieht denn dein Ansatz aus? Was hast du bisher?



  • Ein Algorithmus, der in $$\mathcal{O}(n^2)$$ abläuft (und daher subobtimal ist) wäre die Zykluslänge 1 auszuprobieren, dann mit 2, dann mit 3, usw. bis mit n. Sobald eine Übereinstimmung gefunden wurde, gib sie aus, bei keiner ist die Zeichenkette nicht zyklisch.

    Besser wäre vermutlich, den ersten Buchstaben zu suchen und dort kleine Substrings zu starten. Dann weiter mit dem zweiten Buchstaben und alle Substrings, die eine Abweichung aufzeigen, verwirfst du. Sobald die Ursprungsfolge eine andere erreicht, kannst du Bilanz ziehen. IMHO geht das in $$\mathcal{O}(n)$$.



  • #include <algorithm> // std::min
    #include <algorithm> // find
    #include <iostream>
    #include <string>
    
    int zykluslaenge( const std::string& txt ) 
    {
        if( txt.empty() )
            return -1;
        char first = *txt.begin();
        for( std::string::const_iterator i = find( txt.begin() + 1, txt.end(), first ); i != txt.end(); i = find( i + 1, txt.end(), first ) )
        {
            bool zyklus = true;
            int zl = i - txt.begin();
            for( int start = zl; start < int(txt.length()); start += zl )
            {
                int len = std::min( zl, int(txt.length() - start) );
                if( txt.substr( start, len ) != txt.substr( 0, len ) )
                {
                    zyklus = false;
                    break;
                }
            }
            if( zyklus )
                return zl;
        }
        return -1;
    }
    
    int main()
    {
        using namespace std;
        cout << "geben Sie eine Zeichenfolge ein (Ende mit 'q')" << endl;
        for( string text; cout << "Eingabe: ", cin >> text && text != "q"; )
        {
            int zl = zykluslaenge( text );
            if( zl < 0 ) cout << "nicht zyklisch ";
            else cout << "Zykluslaenge " << zl;
            cout << endl;
        }
        return 0;
    }
    

    so ?

    geben Sie eine Zeichenfolge ein (Ende mit 'q')
    Eingabe: abcabca
    Zykluslaenge 3
    Eingabe: abcabcd
    nicht zyklisch
    Eingabe: abcaabcab
    Zykluslaenge 7
    Eingabe: abcaabcaa
    Zykluslaenge 4
    Eingabe: abcd
    nicht zyklisch
    Eingabe: q
    

    Gruß
    Werner



  • Ich wuerde jeden Buchstaben zaehlen und aus der Verteilung ablesen, welche Zykluslaengen in Frage kommt. Und aus diesen dann weiter aussortieren. Sie muss z.B. ein Teiler der Laenge des Strings sein.

    abaccabacc... mag die Verteilung a🅱c = 200💯200 sein und der String 500 lang. Mit dem groessten gemeinsamen Teiler 100 aller drei Zahlen und erhaelt 2:1:2 (Zyklus 5). Nun kann man anfangen durchzuprobieren. Dabei brauchen nur solche getestet werden, deren Zykluslaenge ein Teiler von 500 ist. Z.b ist 6:3:6 mit Laenge 15 kein Zyklus, da 15 kein Teiler von 500 ist.

    Edit: Ich habe nicht gesehen, dass der letzte Zyklus auch unvollstaendig sein kann. Dann hilft dir der Teilertrick nichts, und du musst alle moeglichen Zykluslaengen testen.

    Besser wäre vermutlich, den ersten Buchstaben zu suchen und dort kleine Substrings zu starten. Dann weiter mit dem zweiten Buchstaben und alle Substrings, die eine Abweichung aufzeigen, verwirfst du. Sobald die Ursprungsfolge eine andere erreicht, kannst du Bilanz ziehen. IMHO geht das in O(n)

    Und wenn man sehr lange Strings hat ... diese Variante wuerde wahrscheinlich sehr viel Speicher fressen.



  • Ihr macht's euch ja ganz schön umständlich.

    Ich scheue mich, ohne erbrachte Eigenleistung des Threaderstellers hier eine Lösung reinzustellen, aber eigentlich ist das ein ziemlich simples Problem, wenn man den Modulo-Operator kennt. Iteratoren und Substrings scheinen mir ziemlich große Kanonen für ziemlich kleine Spatzen.

    Übrigens lässt sich Ansetzers Ansatz leicht zu O(n) runterdrücken, wenn man sich klarmacht, dass man, wenn man etwa einen Zyklus der Länge 4 prüft und am 9ten Zeichen feststellt, dass dieser nicht hält, Zyklen der Längen 5-8 nicht mehr prüfen muss.



  • Nachtrag: Ich habe mit mit der O(n)-Geschichte geirrt, mea culpa. "aabaaaba" hat mich da kalt erwischt.

    Also, O(n * f(n)), mit O(f(n)) < O(n). Trotzdem ist das mit Modulo deutlich einfacher zu haben.



  • @seldon: Was machst du mit der Folge "abcdefg"?
    Also O(n·f(n)), mit O(f(n)) ≤ O(n) und somit im schlechtesten Fall O(n²). Hat nichts gebracht.

    Mein zweiter Ansatz wird übrigens nicht mit substring() gemacht (auch wenn das so herüberkommt), sondern ich habe eher an std::vector<std::string::iterator> gedacht. Im Grossen und Ganzen entspricht er der Umsetzung Werner Salomon, nur ist er etwas zeitoptimierter (O(n) anstatt O(n²)) benötigt dafür jedoch er mehr Speicher.



  • Ansetzer schrieb:

    @seldon: Was machst du mit der Folge "abcdefg"?
    Also O(n·f(n)), mit O(f(n)) ≤ O(n) und somit im schlechtesten Fall O(n²). Hat nichts gebracht.

    Mein zweiter Ansatz wird übrigens nicht mit substring() gemacht (auch wenn das so herüberkommt), sondern ich habe eher an std::vector<std::string::iterator> gedacht. Im Grossen und Ganzen entspricht er der Umsetzung Werner Salomon, nur ist er etwas zeitoptimierter (O(n) anstatt O(n²)) benötigt dafür jedoch er mehr Speicher.

    Im Fall von "abcdefg" muss ich für jede Zyklenlänge nur ein Zeichen prüfen, um festzustellen, dass der Zyklus nicht hält, und kriege dementsprechend O(n). Interessanter ist der Fall "aaaaaaaaaab", in dem es bei völlig naiver Implementation tatsächlich auf O(n²) hinausliefe (allerdings nicht bei mir), oder pathologische Fälle wie "aaabaaaaaaaaaaaaabaaaaaaaaaaaaabaaaaa", in denen ich auch keinen einfachen Weg zu O(n) sehe.

    Vielleicht ließe sich mit Boyer-Moore-artigen Tricks etwas drehen, die Laufzeitkomplexität zu drücken, aber das auszuklamüsern ist mir hierfür entschieden zu viel Arbeit.



  • Danke euch leute, für die antworten und dass ihr mir dabei helft 🙂

    nun ja mit den ansätzen sieht es bei mir nicht gut aus. ich bin programmieranfänger und bin bei der aufgabe echt verzweifelt...

    die lösung von Werner stimp zwar, aber damit kann ich auch nichts anfangen, weil das viel zu kompliziert gelöst ist... kann man das nicht auch einfacher ausführen?



  • Mache dir doch bitte selbst mal Gedanken. Welche schritte musst du mache? Das ganze zu Programmieren kommt erst am Ende.

    Wie wuerdest du auf Zykluslaenge 1 testen?
    Wie wuerdest du auf Zykluslaenge 2 testen?
    Wie wuerdest du auf Zykluslaenge 3 testen?

    ... kann man das dann verallgemeinern? Wie?

    Auch wuerde ich das nicht gelten lassen:

    Eingabe: abcaabcab
    Zykluslaenge 7
    


  • abcaabcab hat doch eine Zykluslänge von 7!?
    4 ist es jedenfalls nicht:

    abca
        abca
            b
    

    Welche meintest du dann?



  • Naja, ich braeuchte schon mindestens eine Wiederholung, sonst ist es kein Zyklus.


Log in to reply