Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


19. Suchen in Zeichenfolgen



Übungen

  1. Implementieren Sie einen groben Algorithmus für Pattern Matching, der das Muster von rechts nach links durchsucht.
  2. Geben Sie die Tabelle next für den Algorithmus von Knuth-Morris-Pratt für das Muster AAAAAAAA an.
  3. Geben Sie die Tabelle next für den Algorithmus von Knuth-Morris-Pratt für das Muster ABRACADABRA an.
  4. Zeichnen Sie einen endlichen Automaten, welcher das Muster ABRACADABRA suchen kann.
  5. Wie würden Sie eine Textdatei nach einer Zeichenfolge aus 50 aufeinanderfolgenden Leerzeichen durchsuchen?
  6. Geben Sie die Sprungtabelle skip für das Durchsuchen von rechts nach links für das Muster ABRACADABRA an.
  7. Konstruieren Sie ein Beispiel, für das das Durchsuchen des Musters von rechts nach links bei ausschließlicher Verwendung der heuristischen Methode der Nichtübereinstimmung ein schlechtes Verhalten aufweist.
  8. Wie würden Sie den Algorithmus von Rabin-Karp modifizieren, wenn nach einem gegebenen Muster unter der zusätzlichen Bedingung gesucht werden soll, daß das mittlere Zeichen ein »Joker« ist (jedes beliebige Textzeichen kann mit ihm übereinstimmen)?
  9. Implementieren Sie eine Variante des Algorithmus von Rabin-Karp für die Suche von Mustern in zweidimensionalem Text. Dabei werde angenommen, daß sowohl Muster als auch Text aus Zeichen gebildete Rechtecke sind.
  10. Schreiben Sie Programme für die Erzeugung einer zufälligen, 1000 Bits umfassenden Text-Zeichenfolge und für das anschließende Auffinden aller Vorkommen der letzten k Bits, für k = 5, 10, 15. (Für unterschiedliche Werte von k können unterschiedliche Methoden zweckmäßig sein.)


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]