Subcadena repetida no superpuesta más larga que utiliza Suffix Tree/Array (Algoritmo solamente)

Question

Necesito encontrar la subcadena repetida no superpuesta más larga en una cadena. Tengo el conjunto de sufijo y sufijo de la cadena disponible.

Cuando se permite la superposición, la respuesta es trivial (nodo principal más profundo en el árbol de sufijos).

Por ejemplo, para String = "acaca"

si se permite que Solapamiento respuesta es "ACA", pero cuando la superposición no está permitido respuesta es "ac" o "ca".

Necesito el algoritmo o la idea de alto nivel solamente.

P.S .: Lo intenté, pero no hay una respuesta clara que pueda encontrar en la web.

Answer 1

La solución más simple es algo así como un ataque de fuerza bruta. Tiene un algoritmo para encontrar la cadena superpuesta permitida más larga, úselo, compruebe si la respuesta se superpone, en caso afirmativo, encuentre la segunda más larga, compruebe y vea si se superpone, y así sucesivamente. Eso lo reduce a su algoritmo de búsqueda existente, luego una operación de recuento de expresiones regulares.

Answer 2

Esto podría resolverse usando resultados dados en "Cálculo más largos Factores que no se solapan anteriores" (ver http://dx.doi.org/10.1016/j.ipl.2010.12.005)

Answer 3

Desafortunadamente, la solución propuesta por Perkins no funcionará. No podemos abrirnos camino a fuerza de soluciones para encontrar una subcadena repetida que no se superpone. Considere el árbol de sufijo para plátano: http://en.wikipedia.org/wiki/Suffix_tree. El nodo de bifurcación "NA" con "A" como su elemento primario se considerará primero, ya que tiene la mayor longitud y es un nodo de bifurcación. Pero su cadena construida "ANA" se superpone, por lo que será rechazada. Ahora, el siguiente nodo a considerar con ser "NA" que mostrará una longitud no superpuesta de 2, pero la subcadena "AN" nunca se considerará ya que ya se representó en la cadena ANA ya considerada. Entonces, si estás buscando todas las subcadenas repetidas que no se superponen, o cuando hay una corbata que quieres la primera alfabética, no tienes suerte.

Al parecer hay un enfoque que implica sufijo árboles que funciona, pero el enfoque más simple se presenta aquí: http://rubyquiz.com/quiz153.html

Espero que esto ayude!

Answer 4

Genera matriz de sufijos y ordena en O (nlogn) .ps: Hay algoritmos más efectivos como algoritmos DC3 y Ukkonen. ejemplo:

Cadena: ABABC arreglo de sufijos: puesta en el índice de subcadena | subcadena
0 - ABABC
2 - abc
1 - BABC
3 - bc
4 - c

---

comparar cada dos subcadena consecutiva y obtener prefijo común con siguiente restricción:
Say i1 es el índice de subcadena "ABABC":
dicen i2 es el índice de subcadena "abc ":
prefijo común es" ab", la longitud de prefijo común se len

---

abs (i1-i2)> len // evitar la superposición

---

vaya a través de la matriz de sufijos con solución, y obtendrá el resultado de "ababc", que es "ab";

La solución entera se ejecutará O (nlogn)

Sin embargo, habrá un caso especial: "aaaaa" que esta solución no puede resolver a fondo.
Bienvenido a discutir y llegar a una solución de O (nlogn) pero no O (n^2)

Answer 5

Mediante la construcción de un árbol de sufijos, todos los sufijos que comparten un prefijo P serán descendientes de un ancestro común en el árbol . Al almacenar el índice máximo y mínimo de los sufijos de ese subárbol, podemos garantizar una subcadena repetitiva que no se superpone de longitud min (profundidad, máx.-Mín.) Donde max-min es la distancia entre ellos y la profundidad es la longitud de su prefijo común. El valor deseado es el nodo con dicho valor máximo.

Answer 6

Código completo:

#include <bits/stdc++.h> 
using namespace std; 
int cplen(string a,string b){ 
    int i,to=min(a.length(),b.length()); 
    int ret=0; 
    for(i=0;i<to;i++){ 
     if(a[i]==b[i])ret++; 
     else { 
      return ret;} 
     } 
    return ret; 
    } 
int main(){ 
    { 
     int len,i; 
     string str; 
     cin>>str; 
     len=str.length(); 
     vector<pair<string,int> >vv; 
     map<char,int>hatbc; 
     string pp=""; 
     for(i=len-1;i>=0;i--){ 
      hatbc[str[i]]++; 
      pp=str.substr(i,len-i); 
      vv.push_back(make_pair(pp,i)); 
      } 
     if(len==1 || (int)hatbc.size()==len){ 
      printf("0\n"); 
      continue; 
      } 
     if(hatbc.size()==1){ 
      printf("%d\n",len/2); 
      continue; 
      } 
     char prev=str[0]; 
     int foo=1,koo=0; 
     for(i=1;i<len;){ 
      while(str[i]==prev && i<len){i++;foo++;} 
      prev=str[i]; 
      i+=1; 
      if(koo<foo)koo=foo; 
      foo=1; 
      } 

     sort(vv.begin(),vv.end()); 
     int ans=0; 
     ans=koo/2; 
     for(i=1;i<(int)vv.size();i++){ 
      int j=i-1; 
      int a=vv[j].second,b=vv[i].second; 
      string sa=vv[j].first,sb=vv[i].first; 
      int cpl; 
      cpl=cplen(sa,sb); 
      if(abs(a-b)>=cpl) 
       ans=max(ans,cpl); 
      } 
     printf("%d\n",ans); 
     } 
    return 0; 
    } 

Complejidad: O (n * log (n)) (debido a la clasificación)

Answer 7

Utilizamos la matriz longest common prefix (LCP) array y el sufijo para resolver este problema en O (log n n) tiempo

La matriz LCP nos da el prefijo común más largo entre dos sufijos consecutivos en la matriz de sufijos.

Después de construir la matriz LCP y la matriz de sufijos, podemos buscar binariamente la longitud de la respuesta.

Supongamos que la cadena es "acaca $". La matriz de sufijos se da en el fragmento de código como una tabla.

<table border="1"> 
 
<tr><th>Suffix Array index</th><th>LCP</th><th>Suffix (implicit)</th></tr> 
 
<tr><td>5</td><td>-1</td><td>$</td></tr> 
 
<tr><td>4</td><td>0</td><td>a$</td></tr> 
 
<tr><td>2</td><td>1</td><td>aca$</td></tr> 
 
<tr><td>0</td><td>3</td><td>acaca$</td></tr> 
 
<tr><td>3</td><td>0</td><td>ca$</td></tr> 
 
<tr><td>1</td><td>2</td><td>caca$</td></tr> 
 
</table>

búsqueda binaria

Vamos por la duración de la respuesta.

Si tenemos una respuesta determinada, dejemos que las dos subcadenas correspondan a dos sufijos.

No hay garantía de que estos sufijos sean consecutivos en la matriz de sufijos. Sin embargo, si conocemos la longitud de la subcadena, podemos ver que cada entrada en la tabla LCP entre los dos sufijos de las subcadenas es al menos ese número. Además, la diferencia entre los índices de los dos bastantes debe ser al menos ese número.

Suponiendo que la longitud de la subcadena es una cierta cantidad, podemos considerar ejecuciones consecutivas de entradas de matriz LCP que son al menos esa cantidad. En cada ejecución consecutiva, encuentre el sufijo con el índice más grande y el más pequeño.

¿Cómo sabemos que nuestra conjetura es un límite inferior?

Si la distancia entre el índice más grande y el más pequeño en algunas [ejecuciones consecutivas de las entradas de la matriz LCP que son al menos nuestra suposición] es al menos nuestra suposición, entonces, nuestra conjetura es un límite inferior alcanzable.

¿Cómo sabemos que nuestra suposición es demasiado grande?

Si la distancia entre el índice más grande y el más pequeño en todas [las ejecuciones consecutivas de las entradas de la matriz LCP que son al menos nuestra suposición] es menor que nuestra conjetura, entonces, nuestra suposición es demasiado grande.

¿Cómo encontramos la respuesta dada la duración de la respuesta?

Para cada [carreras consecutivas de entradas de matriz LCP que son al menos la respuesta], encuentre los índices más bajo y más alto. Si difieren por lo menos en la respuesta, entonces volvemos que las subcadenas repetidas no superpuestas más largas comienzan en estos índices.

En su ejemplo, "acaca $", podemos encontrar que la duración de la respuesta es 2.

Todas las pistas son: "aca $", "acaca $", y la distancia entre el los índices más bajos y más altos son 2, lo que da como resultado la subcadena repetida "ac".

"caca $", "ca $", y la distancia entre los índices inferior y superior es 2, lo que da como resultado la subcadena repetida "ca".