Archive for the ‘Strings suchen’ tag
Algorithmus gesucht: Strings in String suchen
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 »
