Frage zur Lösung bei Stringmatching

NeEn82
Neuling
Neuling
Beiträge: 2
Registriert: 10. Mai 2015 16:56

Frage zur Lösung bei Stringmatching

Beitrag von NeEn82 »

Bei meiner Bearbeitung einer foo-Aufgabe wurden mir in der Lösung 2 Felder rot markiert (in der Spalte von 'b' soll anstelle der 0 eine 2 stehen und in Spalte 't' anstelle der 0 eine 1 stehen).
Leider habe ich beim Nachvollziehen der Korrektur aber ein Problem:
Nehmen wir das Beispiel in Zeile 9. Da muss ein 't' stehen, wodurch sich q wieder verkleinert und in Zeile 1 zurückgesprungen werden soll. Das ist doch aber nur möglich, wenn in diesem Fall der String 'tbtop ygttt' irgendwo auftaucht. Aber dieses Vorkommen von 3 t's in Folge sehe ich nirgends im zu machenden String.
Das gleiche Problem habe ich bei der roten Zelle in Zeile 8. Da müsste ja irgendwo der String 'tbtop ygtb' vorkommen, welchen ich aber auch nicht finde.

Leider kam das bei mir bisher jedes Mal vor und ich scheine auf dem Schlauch zu stehen.
Wenn jemand meinen Fehler finden würde, wäre ich wirklich super dankbar!!
Dateianhänge
Bildschirmfoto 2015-05-09 um 13.06.05.png
Bildschirmfoto 2015-05-09 um 13.06.05.png (49.19 KiB) 733 mal betrachtet
Bildschirmfoto 2015-05-09 um 13.06.21.png
Bildschirmfoto 2015-05-09 um 13.06.21.png (47.61 KiB) 733 mal betrachtet

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: Frage zur Lösung bei Stringmatching

Beitrag von KaeferZuechter »

Der erste Buchstabe im zu suchenden String führt immer zu einem Zustand >= 1.

Kommen wir zu Zustand 8 und dem Buchstaben b:

Ist man in Zustand 8 war der letzte Buchstabe ein t.
Folgt ein b hat man tb und ist somit in Zustand 2 (oder potentiell auch noch höher).


Ich gehe immer wie folgt vor:
1. Laufe den String durch und markiere alle entsprechenden Iterationen mit i+1.
2. Suche möglichst lange Wiederholungen der Substrings zu Beginn und ergänze den Folgebuchstaben in der passenden Iteration.
3. Ergänze alle freien Felder des Anfangsbuchstaben um 1.

Beispiel zu 2: ("Wert" bezeichnet Folgezustand)
- String beginne mit abac
- Überall, wo der Substring aba auftaucht und nicht c folgt, hat c den "Wert" 4 (sofern noch kein höherer Wert gefunden)
- Überall, wo ein a steht und kein b folgt hat b den "Wert" 2 (sofern noch kein höherer Wert gefunden)

Da wir Menschen mit unseren extrem parallelisierten Superrechnern im Kopf solche sich wiederholenden Substrings auf einen Blick sehen, ist diese Methode sehr schnell.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

NeEn82
Neuling
Neuling
Beiträge: 2
Registriert: 10. Mai 2015 16:56

Re: Frage zur Lösung bei Stringmatching

Beitrag von NeEn82 »

Danke :)

Antworten

Zurück zu „Archiv“