Finden Sie eine Liste von Mustern in einem Eingabestrom

Question

Angenommen, Sie haben einen Eingabezeichenstrom (StreamReader) und Sie haben eine Liste von Mustern wie ABCAS, ASGKT. KHTSD usw. Sie müssen den Stream einzeln lesen, und Sie müssen die Anzahl der bisher gefundenen Muster zählen. Wenn EOF auftritt, drucken Sie einfach alle Muster zusammen mit count.

Beispiel:

Eingabestring: 011.100.010
Muster 1: 011
Muster 2: 010

Output:
011 => 1
010 => 1

Answer 1

Es gibt bestehende Tools zur Lösung dieses Problems. Sie heißen lexers, und eines der bekanntesten Beispiele ist lex, in den Kommentaren erwähnt.

Allerdings, wenn Sie es selbst implementieren müssen, Aho-Corasick Algorithmus tut die Sache. Gegeben eine Menge von Strings S = s_1, ..., S_K der Gesamtlänge L, baut es eine trie auf diesen Saiten und macht einen Automaten auf der Grundlage dieser trie. Jetzt füttern Sie Ihre Eingabe-Zeichenfolge in diesen Automaten. Zu jeder Zeit ist es in der Lage, Ihnen die Reihe von Strings von S zu geben, die an der aktuellen Position enden, mit der Zeit proportional zur Anzahl solcher Strings.

Zum Beispiel, wenn S = { "aba", "bababa", "ba", "ABACABA"} und Sie haben die Zeichenfolge rabacaba eingegeben wird, wird der Ausgang des Algorithmus seine {0, 2, 3} (die Indizes der Strings, die an der letzten gefütterten Position enden).

Mit einer solchen Struktur, Wartung aufgetretene Zeichenfolgen und ihre Anzahl ist einfach: nur eine Abfrage auf die Struktur nach jedem Zeichen des Streams.