Para encontrar toda la subcadena que se repite en una cadena dada

Question

Recién encuentro una pregunta de la entrevista: Para encontrar toda la subcadena repetitiva en una cadena dada con un tamaño mínimo de 2. El algoritmo debe ser eficiente.

El código para la pregunta anterior se proporciona a continuación, pero no es eficiente.

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <set> 
#include <string> 

using namespace std; 

int main() 
{ 
    typedef string::const_iterator iterator; 
    string s("ABCFABHYIFAB"); 
    set<string> found; 

    if (2 < s.size()) 
     for (iterator i = s.begin() + 1, j = s.end(); i != j; ++i) 
      for (iterator x = s.begin(); x != i; ++x) 
      { 
       iterator tmp = mismatch(i, j, x).second;; 
       if (tmp - x > 1) 
        found.insert(string(x, tmp)); 
      } 

      copy(found.begin(), found.end(),ostream_iterator<string>(cout, "\n")); 
} 

Mi pregunta es que, ¿hay alguna estructura de datos que se pueden aplicar pregunta anterior en el tiempo complejidad de O (N)?

Si su respuesta es Árbol de sufijo o Hashing, por favor, ejecútelo.

Answer 1

Si se analiza la salida de la cadena de "AAAAAAAAAAAAAA", entonces hay O (N ²) personajes en él, por lo que el algoritmo es al menos O (N ²).

Para lograr O (n²), simplemente construya el suffix tree para cada sufijo de s (índices [1..n], [2..n], [3..n], ..., [n. .norte]). No importa si una de las cadenas no tiene un nodo final propio, simplemente cuente con qué frecuencia se utiliza cada nodo.

Al final, itere sobre cada nodo con conteo> 1 e imprima su ruta.

Answer 2

Eso es solo una idea disparatada, pero vale la pena intentarlo (sin embargo, consume O (N) memoria, donde N es la longitud de la cadena primaria). El algoritmo no es O (N), pero tal vez se puede optimizar.

La idea es que no desea hacer comparaciones de cadenas a menudo. Puede recopilar el hash de datos leídos (por ejemplo, una suma de códigos ASCII de caracteres leídos) y comparar los valores hash. Si los valores hash son iguales, las cadenas pueden ser iguales (debe verificarse más adelante). Por ejemplo:

ABCAB 

A -> (65) 
B -> (131, 66) 
C -> (198, 133, 67) 
A -> (263, 198, 132, 65) 
B -> (329, 264, 198, 131, 66) 

Debido a que usted está interesado únicamente en 2+ valores de longitud, hay que omitir el último valor (porque siempre se corresponde con el carácter individual).

Vemos dos valores iguales: 131 y 198. 131 significa AB y revela el par, sin embargo, 198 significa tanto ABC como BCA, que deben rechazarse mediante comprobación manual.

Esa es solo la idea, no la solución en sí misma. La función hash puede extenderse para tener en cuenta la posición del carácter en la subcadena (o la estructura de la secuencia). El método de almacenamiento de los valores hash se puede cambiar para mejorar el rendimiento (sin embargo, en el costo de un mayor uso de la memoria).

Espero que me ayudó un poco :)

Answer 3

no sé qué árbol de sufijos puede obtener toda la subcadena que se repite, cadena "Mississippi" construir árbol de sufijos como esto:

lo siento, veo. "Al final, itere sobre cada nodo con conteo> 1 e imprima su ruta". "count" es la cantidad de este nodo hijo

tree-->|---mississippi    m..mississippi 
     | 
     |---i-->|---ssi-->|---ssippi i .. ississippi 
     |  |   | 
     |  |   |---ppi  issip,issipp,issippi 
     |  | 
     |  |---ppi    ip, ipp, ippi 
     | 
     |---s-->|---si-->|---ssippi s .. ssissippi 
     |  |  | 
     |  |  |---ppi  ssip, ssipp, ssippi 
     |  | 
     |  |---i-->|---ssippi  si .. sissippi 
     |    | 
     |    |---ppi  sip, sipp, sippi 
     | 
     |---p-->|---pi     p, pp, ppi 
       | 
       |---i     p, pi 

--- Suffix Tree for "mississippi" --- 

Answer 4

Creo que este problema también se puede resolver mediante la programación dinámica.