Zum Inhalt springen

Empfohlene Beiträge

Geschrieben

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

Geschrieben

ä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

Geschrieben

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

Geschrieben

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.

Geschrieben

@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.

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.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...