Declaración informal del problema:
Dada una cadena, por ejemplo, , queremos colorear algunas letras rojas y algunas letras azules (y algunas no en absoluto), de modo que leer solo las letras rojas de izquierda a derecha arroje el mismo resultado que leer solo las letras azules.
En el ejemplo podríamos colorearlos así:
Por lo tanto, decimos es una subsecuencia repetida de . También es una subsecuencia repetida más larga (que es fácil de verificar).
¿Podemos calcular subsecuencias repetidas más largas de manera eficiente?
Pregunta formal
¿Es NP-difícil decidir por una cadena y algo de , si existe una subsecuencia repetida de longitud en la cadena?
- Si es así: ¿Qué problema puede reducirse a este problema?
- Si no: ¿Qué es un algoritmo eficiente? (obviamente, este algoritmo se puede usar para calcular una subsecuencia repetida más larga)
Pregunta extra:
¿Será siempre una subsecuencia repetida de longitud si el tamaño del alfabeto está limitado por una constante?
(Se sabe que esto es cierto para los alfabetos binarios).
Edición 2: La respuesta negativa a la pregunta de bonificación ya se conoce para alfabetos de tamaño mínimo de . De hecho, para alfabetos de tamaño , hay cadenas con subsecuencias repetidas más largas de una longitud meramente . Cadenas aleatorias son suficientes para mostrar esto. El resultado ya existía, pero lo pasé por alto. O ( n · Σ - 1 / 2 )
Editar: Nota:
Algunas personas quieren decir "subcadena" cuando dicen "subsecuencia". Yo no. Este no es el problema de encontrar una subcadena dos veces.
Respuestas:
Esto se puede resolver enG (i,j) S S[i]=S[j] u v u v
tiempo polinomialconstruyendo un gráfico donde cada nodo representa un punto en alguna subsecuencia repetida de tal que . El borde entre los nodos y significa que puede continuarse por para formar una subsecuencia repetida de longitud 2.( i , j ) S S [ i ] = S [ j ] u v u v1. Encuentra los nodos. Esto se puede hacer en tiempo construyendo una lista ordenada de índices para cada carácter , y luego enumerando los pares únicos. No hay más de nodos.c m = n 2O(n2) c m=n2
2. Encuentra los bordes. A lleva tiempo verificar si el nodo puede continuar con el nodo , por lo que al considerar todos los pares este paso lleva tiempo .u v ( u , v ) O ( m 2 )O(1) u v (u,v) O(m2)
3. Tenga en cuenta que la ruta más larga en puede no ser una subsecuencia repetida válida. Considere los caminos y . Si existe un borde entonces es una subsecuencia repetida válida de longitud 3. Por lo tanto, toma tiempo para encontrar todas las subsecuencias repetidas de longitud 3. En el caso general, se necesita tiempo lineal para verificar si dos rutas válidas de longitud se puede combinar en una ruta válida de longitud .a b b c a c a b c O ( m 4 ) n n + 1G ab bc ac abc O(m4) n n+1
4. Itere el paso 3 hasta que ya no se puedan encontrar caminos.
fuente