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.
Mit der Zeile j = next[j] habe ich noch Probleme.
Beispiel:
String pattern = "ababcabab";
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?
Also so ganz grundsätzlich verstehe ich, worum es beim Knutz-Morris-Pratt-Algorithmus geht. Nur leider verstehe ich da ein gewisses Detail nicht.
Java:
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;
}
Beispiel:
String pattern = "ababcabab";
Code:
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
Zuletzt bearbeitet: