Mustererkennung in Texten

[lieschen89]

hi,

ich habe ein Wort (enthält nur unterschiedliche Buchstaben) und einen Text und soll überprüfen ob das Wort in dem Text vorkommt

Die einfachste Methode wäre ja einfach an jeder Stelle des Textes zu überprüfen ob das Wort passt. Das braucht aber O(|t| * |m|) Schritte,

ich soll es aber in O(|t|) Schritten hinbekommen, und habe keine Ahnung wie

kann mir vll jemand weiter helfen?

wäre echt super dankbar

[flashpixx]

Das Stichwort wäre "Suffix-Tree" und Algorithmus von Ukkonen's algorithm - Wikipedia, the free encyclopedia

[lieschen89]

ähm, ok, danke für die schnelle Antwort, aber das ist glaube ich nicht das was ich suche

hatte vergessen zu erwähnen, dass ich diesen einfachen Algorithmus, also einfach an jeder Stelle des Textes zu vergleichen, modifizeren soll, so dass ich nur noch eben O(|t|) Schritte brauche

[lieschen89]

was mir jetzt als Lösung eingefallen ist, bin mir aber nicht sicher wegen der Laufzeit, ähm, wäre dass man eben, da ja beim Muster alle Buchstaben/Zeichen verschieden sein müssen, wenn man als Wort bspw. abcdef hat

und als Text: abcdghtggajttab

wenn man dann den ersten Buchstaben vergleicht, a = a , passt, den zweiten, b= b , passt den dritten c=c, d=d, und dann fünften: g =/ f, passt nicht

Dass man dann nicht wieder in dem Text beim zweiten Buchstaben weitermacht mit vergleichen, sondern eben beim fünften

(weil ja die Buchstaben im Wort unterschiedlich sein müssen, und so gewährleistet ist, dass keiner der Buchstaben die überinstimmten wieder der erste Buchstabe des Wortes sein können)

^^hoffe das war irgendwie verständlich

weiß nur nicht wie das mit der Laufzeit aussieht

[flashpixx]

hatte vergessen zu erwähnen, dass ich diesen einfachen Algorithmus, also einfach an jeder Stelle des Textes zu vergleichen, modifizeren soll, so dass ich nur noch eben O(|t|) Schritte brauche

Suchen != Modifzieren, bevor Du modifizieren kannst musst Du erst einmal suchen, das sind zwei unabhängige Sachen. Bitte lies den verlinkten Algorithmus und evtl die ursprüngliche Quelle. Zurzeit ist für eine solche Suche kein schnellerer Algorithmus bekommt, der Algorithmus von Ukkonnen ist state-of-the-art für Textsuchen, sofern keine anderen Randbedingungen zur Suche bekannt sind.

[Reinhold]

Ich verstehe Lieschen so, das sie den Algorithmus modifizieren soll ...

[flashpixx]

@Reinhold: Das ist klar, aber sie muss zuerst das Pattern suchen und mit das soll ja in O(n) geschehen (genau das ist ja der Kern des Algorithmus von Ukkonen). Das Einfügen bzw Replacing kann ich auch in linearer Zeit machen, so dass eben Suchen + Ersetzen ebenfalls linear ist.