Preprocessing String Matching BOFA

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Preprocessing String Matching BOFA

Beitrag von tmuecksch »

Hi Leute,

ich weiß ja nicht wie es Euch geht, aber ich finde das Preprocessing bei der Aufgabe bezüglich String Matching BOFA.

Ich hatte eben eine Aufgabenstellung bestehend aus einem Alphabet mit 7 Zeichen und 20 Zuständen von foo vorgesetzt bekommen. Das heißt es gibt 20*7 = 140 Spalten auszufüllen. Ich habe dafür fast eine Stunde gebraucht und am Ende waren einige Fehler drin. Klar; wenn die Tabelle so riesig ist schleichen sich schnell mal Fehler ein.

Also entweder ist foo zu brutal oder ich arbeite einfach zu ineffizient.

Da ersteres bereits diskutiert wurde, muss es also an mir liegen :oops:

Habt Ihr Tipps oder gar ein Verfahren wie Ihr diese Aufgabe verlässlich und schnell löst?

Vielen Dank im Voraus

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: Preprocessing String Matching BOFA

Beitrag von CryNickSystems »

viewtopic.php?f=561&t=32148&p=164604#p164604

Also eine Stunde ist wirklich heftig.

Große Tabellen fülle ich innerhalb von so 4-5min aus.

Du musst außerdem die meisten Zellen gar nicht ausfüllen, da dort ja eh eine 0 reinkäme.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Preprocessing String Matching BOFA

Beitrag von tmuecksch »

Vielen Dank für den Tipp. Damit werde ich es mal versuchen!

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: Preprocessing String Matching BOFA

Beitrag von CryNickSystems »

Ich kann ja mal meine Vorgehensweise für die Tabelle erläutern:

- Zu matchenden String aufschreiben und Indizes durchnummerieren
- Substrings finden und Positionen (gezählt ab 1) von jenen (inkl. Buchstaben) aufschreiben
- Substrings von Blatt in Tabelle übertragen während ich die "normalen" Buchstaben des Matchers durchzähle (beginnend bei 1)
- Zuletzt die Spalte mit dem Anfangsbuchstaben des Matchers komplett mit Einsen (1) befüllen

Ich hoffe, jemand versteht, wie ich das meine :D Vllt. machen das ja sogar einige ähnlich wie ich.

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Preprocessing String Matching BOFA

Beitrag von tmuecksch »

Hi CryNickSystems,

vielen Dank für Deinen Beitrag. Ich habe es nämlich noch nicht gerafft :roll:

Was bedeutet in Deiner Aufzählung: "Substrings finden" ?

CryNickSystems
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 119
Registriert: 30. Apr 2015 18:27

Re: Preprocessing String Matching BOFA

Beitrag von CryNickSystems »

Wiederholungen.

Schau dir mal diese Grafik an:
http://puu.sh/jED1S/908402678a.png

Ich habe dort die Zustandstabelle bereits ausgefüllt und zusätzlich an die Seite den derzeitigen Buchstaben sowie eventuelle Wiederholungen inkl. Zustandszahl notiert.

Hier mal beispielhaft für die ersten vier Buchstaben erklärt:

Code: Alles auswählen

acan
^^^^
1234
(oben die Buchstaben, unten die Zustandszahl)

Wenn jetzt statt dem "n" an 4. Stelle nun ein "c" Stünde, könnte man doch in Zustand zwei, also Substring der Länge 2 gefunden haben?
Daher habe ich als "alternativen Pfad" (wenn man ihn so nennen möchte) bei "c" in Zustand 4 eine "2" eingetragen.

Also ist das alles nichts weiter als Wiederholungen finden ;)

EDIT:
In meiner Grafik fehlt natürlich in der gesamten ersten Spalte (also "a"), wo nichts eingetragen ist, eine 1 :)

tmuecksch
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 123
Registriert: 19. Apr 2013 10:51

Re: Preprocessing String Matching BOFA

Beitrag von tmuecksch »

Hi CryNickSystems,

danke für Deine Hilfsbereitschaft!

[EDIT:] Hab es jetzt gecheckt :D

Antworten

Zurück zu „Archiv“