Buscar la subcadena común más larga de varias cadenas utilizando factor oracle mejorado con matriz LRS

Question

¿Se puede usar un factor-oracle con el sufijo link (paper here) para calcular la subcadena común más larga de varias cadenas? Aquí, subcadena significa cualquier parte de la cadena original. Por ejemplo, "abc" es la subcadena de "ffabcgg", mientras que "abg" no lo es.

He encontrado una forma de calcular la longitud máxima de subcadena común de dos cadenas s1 y s2. Funciona al concatenar las dos cadenas utilizando un carácter que no está en ellas, '$' por ejemplo. Luego, para cada prefijo de la cadena concatenada s con longitud i >= |s1| + 2, calculamos su longitud de LRS (sufijo repetido más largo) lrs[i] y sp[i] (la posición final de la primera aparición de su LRS). Por último, la respuesta es

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|} 

He escrito un programa en C++ que utiliza este método, que puede resolver el problema dentro de 200 ms en mi portátil cuando |s1|+|s2| <= 200000, mediante el oráculo de los factores.

s1 = 'ffabcgg' 
s2 = 'gfbcge' 
s = s1+'$'+s2 
    = 'ffabcgg$gfbcge' 
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 
s: f f a b c g g $ g f b c g e 
sp: 0 1 0 0 0 0 6 0 6 1 4 5 6 0 
lrs:0 1 0 0 0 0 1 0 1 1 1 2 3 0 

ans = lrs[13] = 3 

Sé que los problemas pueden resolverse ambos usando el sufijo-array y el sufijo-árbol con una alta eficiencia, pero me pregunto si hay un método que utiliza factor de Oracle para resolverlo. Estoy interesado en esto porque el factor Oracle es fácil de construir (con 30 líneas de C++, la matriz de sufijos necesita alrededor de 60, y el árbol de sufijos necesita 150), y se ejecuta más rápido que sufijo-matriz y sufijo-árbol.

Puede probar su método del primer problema en this OnlineJudge, y el segundo problema en here.

Answer 1

¿Se puede utilizar un factor de Oracle con el sufijo enlace (papel aquí) para calcular la subcadena común más larga de múltiples hilos?

No creo que el algoritmo sea muy adecuado (está diseñado para factorizar una sola cadena) pero puede usarlo concatenando las cadenas originales con un separador único.

Dada abcdefg y hijcdekl y mncdop, encontrar la subcadena más larga común cd:

# combine with unique joiners 
>>> s = "abcdefg" + "1" + "hijcdekl" + "2" + "mncdop" 
>>> factor_oracle(s) 
"cd" 

Como parte de su algoritmo de tiempo lineal y el espacio, el factor-oráculo redescubrir rápidamente los puntos de ruptura entre las cadenas de entrada como parte de su búsqueda de factores comunes (los únicos que proporcionan las uniones y la señal inmediata para detener la extensión del mejor factor encontrado hasta ahora).