Supongo que desea saber el número total de subcadenas distintas de cada longitud que se comparte.
Puede resolver este problema en tiempo lineal utilizando matrices de sufijos (como parecen sugerir los detalles de la pregunta). Primero, supongamos que ya ha calculado la matriz de sufijos de s1 + | + s2 (donde | es solo algún carácter que no está en s1 o s2) y la matriz LCP.
Ahora supongamos que queremos encontrar el número de cadenas comunes distintas de longitud m. Podemos iterar sobre la matriz de sufijos haciendo un seguimiento de si hemos visto una posición de s1 y s2. Cuando el prefijo común cae por debajo de m (o llegamos al final de la cadena) verificamos si hemos visto un sufijo de ambas cadenas y agregamos 1 si lo hemos hecho. Luego marcamos ambas cadenas como aún no vistas.
- ¿Cuál es el mejor libro para aprender algoritmos genéticos? ¿Por qué?
- ¿Cuál es el mejor algoritmo para encontrar el camino con dos limitaciones?
- Si estudié modelado matemático financiero avanzado en la universidad con un coeficiente intelectual de 145, ¿con qué probabilidad podría construir un algoritmo HFT rentable?
- ¿Cuál es la sobrecarga máxima en el algoritmo de relleno de bytes?
- ¿Cuáles son algunos de los recursos disponibles para los estudiantes de informática en predicción de la estructura secundaria de ARN?
El verdadero truco es hacer esto para todas las longitudes simultáneamente. Para hacerlo, mantendremos un total acumulado (cnt1, cnt2) que indica cuántas veces hemos visto una cadena de s1 y s2 respectivamente, y una pila donde cada entrada en la pila contiene una longitud de prefijo y los valores de cnt1 y cnt2 cuando el prefijo aumentó a ese tamaño.
Ahora, comenzando con el prefijo no vacío, procesamos la matriz de sufijos. Inicializamos cnt1 y cnt2 a 0 y empujamos (len = 0, cnt1 = 0, cnt2 = 0) en nuestra pila.
Cuando procesamos un sufijo, usamos la longitud L como la longitud del prefijo común más largo del sufijo anterior (esto es lo que nos proporciona la matriz LCP) y hacemos el siguiente algoritmo.
1) Si L> = stack.top.len, vaya al paso 6
2) Almacene stack.top como (top_len, top_cnt1, top_cnt2) y luego haga estallar la pila.
3) Si top_cnt1 == cnt1 y top_cnt2 == cnt2 vaya al paso 1
4) Agregue 1 a todos los N valores en el rango [max (L, stack.top.len) + 1, top_len]
5) ve al paso 1
6) Agregue 1 a cnt1 o cnt2 según la cadena desde la que se originó el sufijo actual. Utilice una matriz de sufijo inverso para esto (es decir, mapear las indicaciones de sufijo a las indicaciones de entrada).
7) Si L! = Stack.top.len empuje (L, cnt1, cnt2) sobre la pila
Termine el algoritmo haciendo todos menos los pasos 6 y 7 para L = 0.
Es posible que haya notado que el paso 4 le pide que agregue un valor a un rango. Puede hacer esto en tiempo constante transformando N en su derivada discreta. Solo necesita agregar 1 al comienzo del rango y -1 a uno más allá del final. Luego, al final del algoritmo, puede transformarlo fácilmente en su forma adecuada.
