# Algorithmus um Wiederholungen zu finden



## Djinndrache (8. Jan 2010)

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 (9. Jan 2010)

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 (9. Jan 2010)

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 (9. Jan 2010)

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 (9. Jan 2010)

Servus,



Marco13 hat gesagt.:


> 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 (15. Jan 2010)

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


----------

