lieschen89 Geschrieben 30. November 2010 Geschrieben 30. November 2010 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 Zitieren
flashpixx Geschrieben 30. November 2010 Geschrieben 30. November 2010 Das Stichwort wäre "Suffix-Tree" und Algorithmus von Ukkonen's algorithm - Wikipedia, the free encyclopedia Zitieren
lieschen89 Geschrieben 30. November 2010 Autor Geschrieben 30. November 2010 ä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 Zitieren
lieschen89 Geschrieben 1. Dezember 2010 Autor Geschrieben 1. Dezember 2010 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 Zitieren
flashpixx Geschrieben 1. Dezember 2010 Geschrieben 1. Dezember 2010 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. Zitieren
Reinhold Geschrieben 1. Dezember 2010 Geschrieben 1. Dezember 2010 Ich verstehe Lieschen so, das sie den Algorithmus modifizieren soll ... Zitieren
flashpixx Geschrieben 1. Dezember 2010 Geschrieben 1. Dezember 2010 @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. Zitieren
Empfohlene Beiträge
Dein Kommentar
Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.