AuK/ String matching WS13-14

Wiki-Quelltext dieser Seite.

<language>Java</language>
<language>Java</language>
<language>Java</language>
== Allgemein/Festlegungen ==

String matching befasst sich allgemein mit dem Finden eines Wortes in einem Text. <br>
Beim Text handelt es sich um eine endliche Folge von Zeichen (bestehend aus dem Alphabet der Groß- und Kleinbuchstaben, Zahlen und Satzzeichen) und wird mit ''' ''t'' ''' abgekürzt. Das Wort setzt sich ebenfalls aus den selben Zeichen zusammen und wird abgekürzt als ''' ''w'' ''' dargestellt. Obwohl es aus mehreren Wörtern bestehen kann, wird es im Folgenden als "Wort" bezeichnet.

== Naiver Algorithmus ==

Der Algorithmus sucht und vergleicht Zeichen für Zeichen im Text.

<code id="52d0732515910">
void nativeSuche(String text, String wort){
  int laengeText = text.length();
  int laengeWort = wort.length();		  
  int position = 0;
  int aktZeichen;
  boolean gefunden = false;
  while (position <= laengeText-laengeWort){
  aktZeichen = 0;
    while (aktZeichen < laengeWort && wort.charAt(aktZeichen)==text.charAt(position+aktZeichen))
      aktZeichen++;
    if (aktZeichen == laengeWort){
      System.out.println("Wort an der Stelle " + (position+1) + " im Text gefunden.");
      gefunden=true;
    }
    position++;
  }
  if (gefunden == false)
    System.out.println("Keine Treffer bei der Suche.");
}
</code>

<run id="52d0732515992">
  nativeSuche("Das ist das Haus vom Nikolaus","aus");
</run>

== Weitere Algorithmen ==

Einige weitere Algorithmen.

== Der Boyer-Moore-Horspool Algorithmus ==

Ein sehr bekannter Algorithmus für das String-Matching-Problem.