Algoritmo KMP para hacer coincidir cadenas principales y cadenas de patrones en estructuras de datos", escrito por Yan Wei, tercera edición

En primer lugar, se puede considerar que NEXT es una cuestión de cadena de patrón y no tiene nada que ver con la cadena principal.

Cadena de patrón (alineación) abaabcac

El número de subíndice es 01234567

El valor de next[i] es el prefijo de la cadena de patrón 0~i- 1 El valor máximo de una cadena en la que el primer carácter siguiente[i] y la cadena que consta de los siguientes caracteres[i] son ​​exactamente iguales. Por supuesto, next[i] es menor que la longitud total de la cadena de prefijo.

Ejecuté el programa y el siguiente carácter de esta cadena de patrón es el siguiente:

Carácter de subíndice siguiente[i]

0 a -1

1 b 0

2 a 0

3 a 1

4 b 1

5 c 2

6 a 0

7 c 1

Para next[0] y next[1], sin sentido

next[2], ver antes Dos caracteres ab, el primer 1 es diferente del último 1, por lo que se toma 0.

siguiente[3], para aba, el primer 1 es el mismo que el último 1, pero la longitud 2 es diferente, por lo que siguiente[3]=1.

Y así En, enumere manualmente los valores de longitud de i-2 a 0 e intercepte la cadena de prefijo para comparar.

El cartel decía que next[6]=3 es un error de cálculo. -