Algorithmus um Wiederholungen zu finden

[Djinndrache]

Unabhängig von der Sprache.. Wie kann ich folgendes machen?

Ich habe einen String, der aus ganz vielen einsen und nullen besteht. "1100101010110101010100010101010111..."

Ich möchte nun wissen ob der String sich ab einer bestimmten Stelle wiederholt. Dies könnte aber alle 5 Stellen oder alle 27 Stellen oder sonstwo sein. Es könnte auch sein, dass das gar nicht passiert.

Wie kriege ich das raus?

 

[Marco13]

Du müßtest präziser sein. Der gegebene String wiederholt sich an der Stelle 0, genau 1 mal. (Dort steht eine 1, die dann wiederholt wird). Und ... wahrscheinlich würdest du die Frage nicht stellen, wenn es darum ginge, aber ich frag' trotzdem mal: Geht es um irgendeine Lösung - oder um eine geschickte, schnelle (oder "optimale")...?

 

[Djinndrache]

Es geht um irgendeine Lösung um herauszufinden, an welcher Stelle sich das ganze wiederholt. Und zwar nicht nur einmal sondern immer wieder.
Zum Beispiel würde "111000111000111000" sich nach 6 Stellen immer wieder wiederholen.

 

[Marco13]

Auch wenn die Antwort "Ach neee, SO war das nicht gemeint" schon latent in der Luft liegt: Brute force...

// For [url=http://www.java-forum.org/softwareentwicklung/]Softwareentwicklung - java-forum.org[/url]
// 94330-algorithmus-um-wiederholungen-finden.html#post599322

class Repeat
{

    public static void main(String args[])
    {
        find("123123123");
        find("111000111000111000");
        find("1100101010110101010100010101010111");
    }


    private static String find(String string)
    {
        for (int i=1; i<string.length()/2; i++)
        {
            String head = string.substring(0,i);
            String tail = string.substring(i);

            //System.out.println("Length "+i);
            //System.out.println("head "+head);
            //System.out.println("tail "+tail);

            if (consistsOf(tail, head))
            {
                System.out.println("Found "+head+" repeated in "+string);
                return head;
            }
        }
        System.out.println("No repetition in "+string);
        return null;
    }

    private static boolean consistsOf(String string, String part)
    {
        if (string.length() < part.length())
        {
            return false;
        }
        if (string.equals(part))
        {
            return true;
        }
        String rest = string.substring(part.length());
        return string.startsWith(part) && consistsOf(rest, part);
    }


}

Um Periodizitäten in rationalen Zahlen zu finden gibt's aber bestimmt auch elegantere (und vor allem: effizientere) Möglichkeiten.........

 

[Siassei]

Servus,

Auch wenn die Antwort "Ach neee, SO war das nicht gemeint" schon latent in der Luft liegt: Brute force...
Um Periodizitäten in rationalen Zahlen zu finden gibt's aber bestimmt auch elegantere (und vor allem: effizientere) Möglichkeiten.........

Brute-Force ist wohl die Lösung, was der Fragesteller vermeiden möchte

Ich schließe mich Marco an. Der OP muss mehr Informationen über den konkrete Anwendungsfall geben, sofern dieser eine guten Lösungsansatz bekommen möchte.

Handelt es sich um Strings, währe RegEx eine denkbare Lösung.

 

[MrWhite]

Bitmasken evtl? Könnte für bestimmte Fälle eine super Lösung sein.