endlicher Automat, String-Suche

[DesertEagle]

Hey,

import java.util.BitSet; import java.util.Map; import java.util.HashMap; impo - Pastebin.com

In meinem Projekt geht es darum mithilfe von endlichen Automatenein Pattern in einem String zu suchen.

Nun klappt es, dass ich den 1. Treffer finde.

Also nächstes wollte ich den Code so umschreiben, dass alle Treffer ausgegeben werden. Dafür habe ich eine Schleife geschrieben.

Nun wird die 1. Ausgabe richtig angezeigt, die folgenden sind jedoch falsch.

Es geht um die Methode algorithm. Falls mir jemand helfen könnte wäre das sehr nett.

Danke

 

[SlaterB]

schau dir doch genau an, was deine Schleife macht, was z.B. aus text wird, welches du verkleinerst,
nur eine weiter Ausgabe wie

System.out.println("schleife i: "+i+", max: "+(text.length() - pattern.length())+", text: "+text);

liefert schon Massen an Informationen, nämlich

schleife i: 0, max: 30, text: 0123456789012345678901234567890
Muster tritt mit der Verschiebung 0 auf.
schleife i: 1, max: 29, text: 123456789012345678901234567890
Muster tritt mit der Verschiebung 2 auf.
schleife i: 2, max: 27, text: 3456789012345678901234567890
Muster tritt mit der Verschiebung 5 auf.
schleife i: 3, max: 24, text: 6789012345678901234567890
Muster tritt mit der Verschiebung 9 auf.
schleife i: 4, max: 20, text: 012345678901234567890
Muster tritt mit der Verschiebung 14 auf.
schleife i: 5, max: 15, text: 5678901234567890
Muster tritt mit der Verschiebung 20 auf.
schleife i: 6, max: 9, text: 1234567890
Muster tritt mit der Verschiebung 27 auf.

du verkleinerst text mit jedem Durchlauf umso stärker, nicht vom Ursprungswert, sondern schon vom gekürzten Text, ist das dein Ziel?

beschreibe doch zunächst in Worten, was die Schleife überhaupt leisten soll,
welcher Text untersucht, was im Idealfall gefunden werden usw.

bedenke auch: im Moment wird bei allen rekursiven Aufrufen von erneut algorithm() nichts gefunden, die 'Kein Treffer'-Ausgaben habe ich mal gestrichen,
wenn aber was gefunden werden sollte, dann würden dieses zweite und folgenden algorithm()-Durchläufe auch jeweils eine Schleife durchführen,
da könnte alles mehrfach gefunden werden,

die Schleife gehört vielleicht nicht algorithm(), wird im Moment auch nicht ausgeführt, falls nicht zufällig das erste result klappt

 

[DesertEagle]

Nein, ich merke gerade, dass die Ausgaben auch fehlerhaft sind.

Ich wollte die Schleife so haben, dass er mir den 1. Treffer ausgibt. Dann Zerhackt er an der Stelle Treffer+Patternlänge den durchsuchten String und führt den Algorithmus erneut aus. So erhalte ich alle Treffer im String.

 

[SlaterB]

das ist nicht genau genug,
willst du im aktuellen Beispiel immer genau 1 Zeichen abziehen
0123456789012345678901234567890
123456789012345678901234567890
23456789012345678901234567890
3456789012345678901234567890
oder mehrere wie es aktuell implementiert ist, erst wird 1 Zeichen entfernt, dann 3, dann 6, dann 10 vom Ursprung aus gesehen bzw. 1, 2, 3, 4 immer vom jeweils vorherigen

das sind eigentlich klare Überlegungen, was soll ich da nachfragen, nun schon mehrfach,
du siehst doch selber exakt was passiert

wenn du noch eine Frage hast, dann bitte nicht 'es geht nicht', sondern ganz konkret
'beim zweiten Schleifendurchlauf ist mein Ziel dass Text .. mit Ergebnis .. untersucht wird, ich verstehe nicht wieso .. abgezogen wird' usw.,
ich weiß nämlich nicht was dein Automat macht, ich kann nicht nachvollziehen ob der Code aktuell korrekt oder nicht korrekt ist,
er macht irgendwas, aber was davon richtig und was falsch ist, musst du detailliert darlegen

 

[DesertEagle]

Ich dachte ich hätte es klar ausgedrückt. Sorry dafür.

Nein, er soll nicht immer 1 Zeichen abziehen, das macht keinen Sinn für mich.

Beim zweiten Schleifendurchlauf ist mein Ziel dass der Text der verbleibt, nochmals "untersucht" wird.
Falls er einen weiteren Treffer findet soll er diesen ausgeben. Falls nicht soll er ausgeben, dass es keinen Treffer gibt.
Falls es jedoch einen weiteren Treffer gab, soll er mit den Algorithmus ab der Stelle wo es den Treffer gab nochmals ausführen um nach weiteren Ergebnissen zu suchen.
Ich verstehe nicht, wieso er keinen Treffer anzeigt. Ich verstehe nicht, wieso er die Schleife doch nochmal ausführt, wenn er keinen Treffer ausgibt. Und ich verstehe nicht, wieso er falsche Treffer anzeigt.

Falls das nicht gut genug beschrieben ist tut es mir Leid

Ich versuche es gerade selbst noch...(zu lösen, nicht zu verstehen)


So soll es aussehen:
0123456789012345678901234567890
Treffer an stelle 0
123456789012345678901234567890
Treffer an stelle 10
12345678901234567890
Treffer an stelle 20
usw usf

 

[SlaterB]

oh, einen wichtigen Fehler sehe ich gerade:
der rekursive Aufruf muss

algorithm(text,pattern);
statt
algorithm(pattern,text);
lauten

schau mal wie weit du jetzt kommst, ich mache zunächst noch nichts weiter

 

[DesertEagle]

ok, das ist natürlich ein ärgerlich dummer fehler meinerseits

jetzt erhalte ich eine endlosschleife, er hat treffer über die verschiebung hinaus...

 

[SlaterB]

wie schon gesagt: das erste algorithm() ruft in der Schleife sich selber auf, ob 30x oder nur 7x, jeder dieser Aufrufe führt wieder eine Schleife aus, neue Aufrufe mit neuen Schleifen usw.,

immerhin endet es irgendwann, schnell gezählt komme ich auf 1099165 algorithm()-Aufrufe,
ohne System.out.println() halbwegs schnell durch, mit Ausgaben läuft es natürlich ewig,

keine Schleife in der Rekursion, aber im Detail möchte ich das nicht für dich lösen

 

[DesertEagle]

habe es anders gelöst und hinbekommen, trotzdem vielen dank für die mühe.

lösung poste ich später