Implementierung des Knuth-Morris-Pratt-Algorithmus

[minzee]

Hi 🙂

Also so ganz grundsätzlich verstehe ich, worum es beim Knutz-Morris-Pratt-Algorithmus geht. Nur leider verstehe ich da ein gewisses Detail nicht.

int[] init(String pattern)
{
   int[] next = new int[pattern.length()];
   next[0] = -1;

   int i = 0; // Index Pattern
   int j = -1; // Index Pattern-Kopie (wird von links nach rechts verschoben)

   while(i < pattern.length() - 1)
   {
      while
      (
         j >= 0 &&
         pattern.charAt(i) != pattern.charAt(j)
      )
      {
         j = next[j]; // hierum geht es
      }
      ++i;
      ++j;
      next[j] = j;
   }
   return next;
}

Mit der Zeile j = next[j] habe ich noch Probleme.

Beispiel:

String pattern = "ababcabab";

a|[COLOR="#D3D3D3"]bababcabab[/COLOR]
-+-------
 |[COLOR="#D3D3D3"]ababcabab[/COLOR]

ab|[COLOR="#D3D3D3"]abcabab[/COLOR]
--+------
 [COLOR="#FF0000"]a[/COLOR]|[COLOR="#D3D3D3"]babcabab [/COLOR]... kein match

aba|[COLOR="#D3D3D3"]bcabab[/COLOR]
---+-----
 ab|[COLOR="#D3D3D3"]abcabab [/COLOR]
  [COLOR="#008000"]a[/COLOR]|[COLOR="#D3D3D3"]babcabab [/COLOR]... match

abab|[COLOR="#D3D3D3"]cabab[/COLOR]
----+-----
 [COLOR="#A9A9A9"]aba[/COLOR]|[COLOR="#D3D3D3"]bcabab[/COLOR]
  a[COLOR="#008000"]b[/COLOR]|[COLOR="#D3D3D3"]abcabab [/COLOR]... neben dem vorhergehenden "a" matcht hier auch das "b"

ababc|[COLOR="#D3D3D3"]abab[/COLOR]
-----+----
 [COLOR="#A9A9A9"]abab[/COLOR]|[COLOR="#D3D3D3"]cabab[/COLOR]
  ab[COLOR="#FF0000"]a[/COLOR]|[COLOR="#D3D3D3"]bcabab [/COLOR]... 1) die ersten "ab" waren ein match, das darauffolgende "a" nicht
   [COLOR="#FF0000"]a[/COLOR]b|[COLOR="#D3D3D3"]abcabab [/COLOR]... 2) kein match
    [COLOR="#FF0000"]a[/COLOR]|[COLOR="#D3D3D3"]babcabab [/COLOR]... 3) kein match

Bei 2) hätte ich erwartet, dass das erste "a" im Algorithmus kontrolliert wird. Aufgrund von j = next[j] wird diese Zeile jedoch komplett übersprungen. Nach dem 1) kommt gleich 3) dran. Warum darf man das machen? Warum darf man 2) überspringen?