Как работает префикс функция ?

[videolord]

Привет всем! это алгоритм Кнута-Моррисона-Пратта,нашел код,но ни как не вникаю в этом коде как работает префикс функция prefixFunction(), я знаю теорию и как мы вычисляем префикс функцию но как реализован на jave непонятно,можете комменты поставить в строках кода


Например для abacaba, P("abacaba",i)
P("abacaba", 1) = "a":0
P("abacaba", 2) = "ab":0
P("abacaba", 3) = "aba":1
P("abacaba", 4) = "abac":0
P("abacaba", 5) = "abaca":1
P("abacaba", 6) = "abacab":2
P("abacaba", 7) = "abacaba":3
получаем P("abacaba") =0010123

public class kmp {
  public static int[] prefixFunction(String s) {
  int n = s.length();
  int[] p = new int[n];
  for (int i = 1; i < n; i++) {
  int k = p[i - 1]; // зчем мы присваиваем p[i - 1]
   while (k > 0 && s.charAt(k) != s.charAt(i)){
    k=p[k - 1]; //и здесь?
   }
    p[i] = k + (s.charAt(k) == s.charAt(i) ? 1 : 0);
  }
     return p;
  } 

  public static int kmpMatcher(String s, String pattern) {
    int m = pattern.length();
    if (m == 0) {
      return 0;
    }
    int n = s.length();
    int[] p = prefixFunction(pattern);
    int k = 0;
    for (int i = 0; i < n; i++) {
      while (k > 0 && s.charAt(i) != pattern.charAt(k)) {
        k = p[k - 1];
      }
      if (s.charAt(i) == pattern.charAt(k)) {
        k++;
      }
      if (k == m) {
        return i - m + 1;
      }
    }
    return -1;
  }

  // Usage example
  public static void main(String[] args) {
	  String pattern="abacaba";
	  int[] p = prefixFunction(pattern);
	  for (int i=0;i<7;i++){
	  System.out.print(p[i]);
       }
 	  
}}

[videolord]

нашел еще пример но неясно как мы сравниваем между собой !

Для строки 'abcdabscabcdabia' вычисление будет таким:
'a'!='b' => π=0; 'a'!='c' => π=0; 'a'!='d' => π=0; 'a'=='a' => π=π+1=1; 'b'=='b' => π=π+1=2; 'c'!='s' => π=0; 'a'!='c' => π=0; 'a'=='a' => π=π+1=1; 'b'=='b' => π=π+1=2; 'c'=='c' => π=π+1=3; 'd'=='d' => π=π+1=4; 'a'=='a' => π=π+1=5; 'b'=='b' => π=π+1=6; 's'!='i' => π=0; 'a'=='a' => π=π+1=1;

[legendary]

вроде норм обяснено

[videolord]

ваще не получается скачать
кто нить скиньте на файлообменник пожалуйста!

[videolord]

Спасбо огромное legendary! Классная реализация!Теперь все понятно!