string - algoritmos - kmp algorithm java

Tabla de prefijos KMP

Question

Estoy leyendo acerca de KMP para la coincidencia de cadenas.
Necesita un preprocesamiento del patrón mediante la construcción de una tabla de prefijos.
Por ejemplo, para la cadena ababaca la tabla de prefijos es: P = [0, 0, 1, 2, 3, 0, 1]
Pero no tengo claro qué muestran los números. Leí que ayuda encontrar coincidencias del patrón cuando cambia, pero no puedo conectar esta información con los números en la tabla.

Answer 1

Cada número pertenece al prefijo correspondiente ("a", "ab", "aba", ...) y para cada prefijo representa la longitud del sufijo más largo de esta cadena que coincide con el prefijo. No contamos cadena entera como sufijo o prefijo aquí, se llama auto-sufijo y auto-prefijo (al menos en ruso, no estoy seguro acerca de los términos en inglés).

Así que tenemos una cuerda "ababaca". Veámoslo. KMP calcula la función de prefijo para cada prefijo no vacío. Vamos a definir P[i] como la secuencia de caracteres del patrón donde 0 <= i <= i , 𝝥[i] como la función Prefijo. el prefijo y el sufijo pueden superponerse.

+---+----------+-------+--------+--------+
| i | P[i] | 𝝥[i] | Prefix | Suffix |
+---+----------+-------+--------+--------+
| 0 | a | 0 | | |
| 1 | ab | 0 | | |
| 2 | aba | 1 | a | a |
| 3 | abab | 2 | ab | ab |
| 4 | ababa | 3 | aba | aba |
| 5 | ababac | 0 | | |
| 6 | ababaca | 1 | a | a |
| | | | | |
+---+----------+-------+--------+--------+

Código simple de C ++ que calcula la función de prefijo de la cadena S:

vector<int> PrefixFunction(string S) {
vector<int> p(S.size());
int j = 0;
for (int i = 1; i < (int)S.size(); i++) {
while (j > 0 && S[j] != S[i])
j = p[j-1];
if (S[j] == S[i])
j++;
p[i] = j;
}
return p;
}

Answer 2

Este código puede no ser el flujo de código más corto, pero fácil de entender. Código Java simple para calcular el prefijo-Array-

 String pattern = "ababaca";
int i = 1, j = 0;
int[] prefixArray = new int[pattern.length()];
while (i < pattern.length()) {
while (pattern.charAt(i) != pattern.charAt(j) && j > 0) {
j = prefixArray[j - 1];
}
if (pattern.charAt(i) == pattern.charAt(j)) {
prefixArray[i] = j + 1;
i++;
j++;
} else {
prefixArray[i] = j;
i++;
}
}
for (int k = 0; k < prefixArray.length; k++) {
System.out.println(prefixArray[k]);
}

Produce el resultado requerido

0 0 1 2 3 0 1