Suchalgorithmus für kreisförmige Strings

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo Forum,

ich brauche eine gute Lösung, um ein kreisförmiges String zu durchsuchen. Sagen wir mal ich hab ein String

ABCDEFGHIJ

welches aber nach dem J wieder bei A anfängt usw.
Möchte ich jetzt nach dem Substring

FGH

suchen: Kein Problem. Aber wenn ich jetzt nach

JAB

suchen will?
Meine einzige Idee wäre es, das ganze 2mal hinteinander zu hängen, die Position des Hits zu cachen, und dann die Verdoppelung des Strings wieder rückgängig zu machen.

Irgendwelche besseren Ideen? Ich will das in Perl lösen, aber da es sich um eine allgemeinere Frage handelt, dachte ich, passt es hier ganz gut.

Grüße
Mathias

#2

Hallo!

Meine einzige Idee wäre es, das ganze 2mal hinteinander zu
hängen, die Position des Hits zu cachen, und dann die
Verdoppelung des Strings wieder rückgängig zu machen.

Den doppelten String kannst du ja on-the-fly erzeugen, also ohne Zuweisung an eine Variable. Dann muss du da auch nichts rückgängig machen.

text = "ABCDEFGHIJ"
pos = (text+text).find("JAB")
if pos \>= 0:
 ...

Ist zwar jetzt Python, aber mit Perl geht das sicherlich auch.

Jan

#3

Meine einzige Idee wäre es, das ganze 2mal hinteinander zu
hängen, die Position des Hits zu cachen, und dann die
Verdoppelung des Strings wieder rückgängig zu machen.

Hallo Mathias,

naheliegend, aber bei sorgfältigem Durchdenken nicht ausreichend: der „Kreis“ lautet „A“ und du suchst „AAA“.

Rein mathematisch gesehen, müsstest du den String unendlich oft hintereinander kopieren.

Gruss Reinhard

#4

Hallo!

Rein mathematisch gesehen, müsstest du den String unendlich
oft hintereinander kopieren.

Rein logisch gesehen aber maximal nur so häufig, wie der zu suchende String Zeichen hat.

Jan

#5

Hallo

ich brauche eine gute Lösung, um ein kreisförmiges String zu
durchsuchen. Sagen wir mal ich hab ein String

ABCDEFGHIJ

welches aber nach dem J wieder bei A anfängt usw.
Möchte ich jetzt nach dem Substring

FGH

suchen: Kein Problem. Aber wenn ich jetzt nach

JAB

suchen will?
Meine einzige Idee wäre es, das ganze 2mal hinteinander zu
hängen, die Position des Hits zu cachen, und dann die
Verdoppelung des Strings wieder rückgängig zu machen.

Irgendwelche besseren Ideen? Ich will das in Perl lösen, aber
da es sich um eine allgemeinere Frage handelt, dachte ich,
passt es hier ganz gut.

Ich hab jetzt eine Weile überlegt, was Du tatsächlich
meinen könntest. Möglicherweise sucht Du eine allgemeine
Variante eines periodischen Mappers, also sowas:

[Perl]

...

sub periodic\_mapper {
 my ($where,$len) = @\_;
 return $where \>= $len ? $where - $len : $where
}


my $S = 'ABCDEFGHIJ';
my $L = length $S;
my $N = 3;

for my $x (0 .. $L) {
 print map { substr $S, periodic\_mapper($x+$\_, $L), 1 } 0..$N-1;
 print "\n"
} 

...

Wer weiß? Vielleicht auch etwas anderes. Obiges entspricht einer
Verallgemeinerung, also einer Linearisierung einer nichtlinearen
Sequenz.

Obiges ist natürlich auch mit einer simplen
Modulo-Operation hinzubekommen, also etwa:

...

for my $x (0 .. $L) {
 print map { substr $S, **($x+$\_) % $L**, 1 } 0..$N-1;
 print "\n"
} 

...

aber je nach Randbedingung könnte es auch
„allgemeiner“ ausgedrückt werden müssen.

Grüße

CMБ

#6

naheliegend, aber bei sorgfältigem Durchdenken nicht
ausreichend: der „Kreis“ lautet „A“ und du suchst „AAA“.

Ja ok das würde aber nicht passieren :smile:
Danke trotzdem