PHPGangsta - Der praktische PHP Blog

PHP Blog von PHPGangsta


Archive for the ‘Strings suchen’ tag

Algorithmus gesucht: Strings in String suchen

with 11 comments

Ich habe eine kleine Aufgabe für euch: Gegeben ist ein String, sowie eine Menge kürzerer Strings die darauf geprüft werden ob sie im Ausgangsstring vorkommen und an welcher Stelle. Normalerweise gibt es dafür die PHP-Funktion strpos(). Nehmen wir an sie steht nicht zur Verfügung. Wie würdet ihr das Problem bestmöglich lösen, es gibt ja ziemlich viele Ansätze und Lösungen? Interessant dabei ist dass es exakt einen String gibt den es zu durchsuchen gilt, und sehr viele (hier im Beispiel 10.000) kürzere Strings die es zu suchen gilt. Je nachdem wie man den Algorithmus baut macht es eventuell Sinn einen Index oder ähnliches aufzubauen, sprich anfangs etwas mehr Rechenarbeit zu leisten damit man später die Suche sehr schnell erledigen kann?

Also die Grundstruktur soll wie folgt aussehen (siehe auch bei GitHub):

Weiterlesen »

Written by Michael Kliewe

April 18th, 2012 at 10:17 am

Posted in PHP

Tagged with , ,