Cadena: resuelve la matriz siguiente y la matriz nextval
Cómo resolver la siguiente matriz: Primero, el siguiente valor del primer dígito se le da directamente a 0, y el siguiente valor del segundo dígito se le da directamente a 1. Al resolver el siguiente valor de cada dígito posterior, se debe utilizar el anterior. Primero, compare el bit correspondiente del bit anterior con su siguiente valor. Si son iguales, el siguiente valor del bit es el siguiente valor del bit anterior más 1, si no son iguales, continúe repitiendo este proceso hasta que Se encuentra cierto bit que es igual. Simplemente agregue 1 a su siguiente valor. Si no se encuentra el primer bit, entonces el siguiente valor de ese bit es 1.
Ejemplo:
Otra solución (puedes omitirla si no quieres leerla):
Encuentra la siguiente matriz:
Primero encuentre la cadena de patrón S para cada La longitud máxima común *** y el sufijo de la cadena que precede a un carácter. Esta serie de longitudes se almacena como una matriz. Cada longitud calculada es en realidad el subíndice comparado con cada posición correspondiente de. la cadena de patrón
Por ejemplo: la cadena de patrón es ABACABC, y su matriz de longitud de sufijo y *** común más larga es: Registramos la longitud de sufijo y *** común más larga como LCPSF, ahora comenzando desde primer carácter A de la cadena de patrón, la cadena delante de A es nula, por lo que el LCPSF de la subcadena antes de A es 0 y llega a B, la cadena delante de B es A, A es un solo carácter y no hay ningún carácter; sufijo *** común, por lo que la longitud también es 0; llega a A, la subcadena antes de A es AB y LCPSF es 0, la subcadena antes de C es ABA y LCPSF es 1; la subcadena antes de A es ABAC y LCPSF es 0. Vaya a B, la subcadena antes de B es ABACA y LCPSF es 1. La subcadena antes de C es ABACAB y LCPSF es 2; Sale la matriz de sufijo *** común más larga. Mueva esta matriz desde la segunda. Después de agregar 1 a cada valor comenzando desde el primer valor, obtenemos el subíndice que se comparará con la posición correspondiente de la subcadena, que es la siguiente matriz.
Después de dominar el método anterior para encontrar la siguiente matriz, podemos encontrar rápidamente la siguiente matriz de la cadena de patrón ABACABC. Ahora continúe buscando la matriz de siguiente valor de la cadena de patrón ABACABC:
.Resolver La matriz nextval se basa en la siguiente matriz. El carácter en cada posición de la cadena del patrón se compara con el número de la posición correspondiente del subíndice dado por el siguiente valor de la matriz. El valor de la matriz en next-val se usa como el siguiente del carácter en la posición actual. El valor -val, de lo contrario, toma directamente el valor de la siguiente matriz del carácter en la posición actual como el valor de next-val.
Pasos de solución:
El primer número en la matriz next-val es directamente 0.
El segundo número de next-val: el segundo carácter de la cadena del patrón es B y el segundo número de la matriz de subíndice correspondiente es 1. Eso es para comparar el primer carácter de la cadena del patrón con B. A! = B, así que use directamente el segundo número 1 de la matriz de subíndices como el valor del segundo número de la matriz next-val
El tercer número: el tercer carácter de la cadena del patrón es A. , correspondiente a lo siguiente El tercer número en la matriz de subíndices es 1, tómalo como subíndice, encuentra que el primer carácter de la cadena del patrón es A, A = A, luego toma el primer número de next-val como el valor de tercer número de next-val , es decir, 0
Ejemplo:
Los defectos del siguiente array son los siguientes:
Por ejemplo, la cadena principal es "aabXXXXXXXXXXXXXXX" y la cadena de patrón "aac"
Al calcular la siguiente matriz de "aac" como 012, cuando la cadena de patrón no coincide en el carácter c, saltará al segundo carácter y luego volverá a compárelo con el carácter no coincidente actual de la cadena principal, es decir, aquí Compare la segunda a de la cadena de patrón con la b de la cadena principal, es decir, "aabXXXXXXXXXXXXX" vs "aac Obviamente a no es igual a b". . Luego saltará a 1 y continuará comparando hasta que la coincidencia sea exitosa o la cadena principal se desplace un bit después de que falle la coincidencia.
La matriz nextval de "aac" es 002. Cuando hay una discrepancia en c, saltará a 2. Si todavía hay una discrepancia, saltará directamente a 0, que es una comparación menos. que la siguiente matriz.
Si la cadena del patrón es muy larga, se pueden omitir muchas comparaciones, por lo que usar la matriz nextval es más eficiente que la matriz next.
En el algoritmo KMP para la coincidencia de patrones, el siguiente valor de matriz del patrón (también llamado función de falla en el algoritmo KMP) se define de la siguiente manera:
(1) Cuando j =1, ¿por qué tomar siguiente[1]=0?
Respuesta: Cuando el primer carácter de la cadena del patrón no coincide con un carácter de la cadena principal, el puntero de la cadena principal debe moverse al siguiente carácter. y luego se combina con la cadena de patrón Comparación del primer carácter. (next[1]=0 significa que no hay caracteres en la cadena del patrón que puedan compararse con el carácter actual s[i] en la cadena principal)
(2) ¿Por qué debería max{k} ¿Cuál es el valor máximo de k?
Respuesta: Cuando el carácter i-ésimo de la cadena principal no coincide con el carácter j-ésimo de la cadena de patrón, si la cadena principal i no retrocede, se supone que el carácter k-ésimo en la cadena del patrón coincide con el carácter i-ésimo en la cadena principal. Al comparar caracteres, el valor k debe satisfacer la condición 1 (3) ¿Cuáles son las otras situaciones? ¿Por qué tomar next[j] = 1? Respuesta: En los dos casos anteriores, el puntero de la cadena principal no retrocede. En el peor de los casos, la cadena del patrón comienza desde el primer carácter y la cadena principal. El i-ésimo carácter se compara para que no se pierdan posibles coincidencias.