¿Cómo encontrar la repetición de la secuencia de caracteres en una matriz dada?

Solución de O(NlogN) en la mejilla

Realice un FFT en su cadena (tratando los caracteres como valores numéricos). Cada pico en el gráfico resultante corresponde a una periodicidad de subcadena.

En Python, puedes aprovechar las expresiones regulares así:

def recurrence(text):
    import re
    for i in range(1, len(text)/2 + 1):
        m = re.match(r'^(.{%d})\1+$'%i, text)
        if m: return m.group(1)

recurrence('abcabc') # Returns 'abc'

No estoy seguro de cómo esto se traduciría a Java o C. (Esa es una de las razones por las que me gusta Python, supongo. :-)

Primero escriba un método que encuentre la subcadena repetida sub en la cadena contenedor como se muestra a continuación.

boolean findSubRepeating(String sub, String container);

Ahora sigue llamando a este método con subcadena creciente en el contenedor, primero intenta 1 subcadena de caracteres, luego 2 caracteres, etc. subiendo a container.length/2.

Pseudocódigo

len = str.length
for (i in 1..len) {
   if (len%i==0) {
      if (str==str.substr(0,i).repeat(len/i)) {
         return str.substr(0,i)
      }
   }
}

Nota: Por brevedad, estoy inventando un método "repeat" para cadenas, que en realidad no es parte de la cadena de Java; "abc".repeat(2) = "abcabc"

Usando C++:

//Splits the string into the fragments of given size
//Returns the set of of splitted strings avaialble
set<string> split(string s, int frag)
{
    set<string> uni;
    int len = s.length();
    for(int i = 0; i < len; i+= frag)
    {
        uni.insert(s.substr(i, frag));
    }

    return uni;
}

int main()
{

    string out;
    string s = "carpentercarpenter";
    int len = s.length();

      //Optimistic approach..hope there are only 2 repeated strings
      //If that fails, then try to break the strings with lesser number of
      //characters
    for(int i = len/2; i>1;--i)
    {
        set<string> uni = split(s,i);
        if(uni.size() == 1)
        {
            out = *uni.begin();
            break;
        }
    }

    cout<<out;
    return 0;

}

La primera idea que me viene a la mente es intentar todas las secuencias repetitivas de longitudes que dividen length(S) = N. Hay un máximo de N/2 tales longitudes, por lo que esto resulta en un algoritmo O(N^2).

Pero estoy seguro de que se puede mejorar...

Y aquí hay un ejemplo de trabajo concreto:

/* find greatest repeated substring */
char *fgrs(const char *s,size_t *l)
{
  char *r=0,*a=s;
  *l=0;
  while( *a )
  {
    char *e=strrchr(a+1,*a);
    if( !e )
      break;
    do {
      size_t t=1;
      for(;&a[t]!=e && a[t]==e[t];++t);
      if( t>*l )
        *l=t,r=a;
      while( --e!=a && *e!=*a );
    } while( e!=a && *e==*a );
    ++a;
  }
  return r;
}

  size_t t;
  const char *p;
  p=fgrs("BARBARABARBARABARBARA",&t);
  while( t-- ) putchar(*p++);
  p=fgrs("0123456789",&t);
  while( t-- ) putchar(*p++);
  p=fgrs("1111",&t);
  while( t-- ) putchar(*p++);
  p=fgrs("11111",&t);
  while( t-- ) putchar(*p++);

Convertiría el array en un objeto String y usaría regex

No estoy seguro de cómo definir "eficientemente". Para una implementación fácil/rápida, puede hacer esto en Java:

    private static String findSequence(String text) {
        Pattern pattern = Pattern.compile("(.+?)\\1+");
        Matcher matcher = pattern.matcher(text);
        return matcher.matches() ? matcher.group(1) : null;
    }

Intenta encontrar la cadena más corta (.+?) que debe repetirse al menos una vez (\1+) para que coincida con todo el texto de entrada.

Ponga todo su carácter en una matriz e. x. a []

i=0; j=0;
for( 0 < i < count ) 
{
if (a[i] == a[i+j+1])
    {++i;}
else
    {++j;i=0;}
}

Entonces la relación de (i/j) = cuenta de repetición en su matriz. Debes prestar atención a los límites de i y j, pero es la solución simple.

Aquí hay una solución más general al problema, que encontrará subsecuencias repetitivas dentro de una secuencia (de cualquier cosa), donde las subsecuencias no tienen que comenzar al principio, ni seguirse inmediatamente.

Dada una secuencia b[0..n], que contiene los datos en cuestión, y un umbral t es la longitud mínima de subsecuencia a encontrar,

l_max = 0, i_max = 0, j_max = 0;
for (i=0; i<n-(t*2);i++) {
  for (j=i+t;j<n-t; j++) {
    l=0;
    while (i+l<j && j+l<n && b[i+l] == b[j+l])
      l++;
    if (l>t) {
      print "Sequence of length " + l + " found at " + i + " and " + j);
      if (l>l_max) {
        l_max = l;
        i_max = i;
        j_max = j;
      }
    }
  }
}
if (l_max>t) {
  print "longest common subsequence found at " + i_max + " and " + j_max + " (" + l_max + " long)";
}

Básicamente:

1. Comience al principio de los datos, itere hasta dentro de 2 * t del final (no hay forma posible de tener dos subsecuencias distintas de longitud t en menos de 2 * t de espacio!)
2. Para la segunda subsecuencia, comience al menos t bytes más allá de donde comienza la primera secuencia.
3. Luego, restablezca la longitud de la subsecuencia descubierta a 0, y verifique si tiene un carácter común en i+l y j+l. Mientras lo haga, incremente l. Cuando ya no tiene un carácter común, ha llegado al final de su subsecuencia común. Si la subsecuencia es más larga que su umbral, imprima el resultado.

Me di cuenta de esto y escribí un código para esto (escrito en C#) con muchos comentarios. Espero que esto ayude a alguien:

// Check whether the string contains a repeating sequence.
public static bool ContainsRepeatingSequence(string str)
{
    if (string.IsNullOrEmpty(str)) return false;

    for (int i=0; i<str.Length; i++)
    {
        // Every iteration, cut down the string from i to the end.
        string toCheck = str.Substring(i);

        // Set N equal to half the length of the substring. At most, we have to compare half the string to half the string. If the string length is odd, the last character will not be checked against, but it will be checked in the next iteration.
        int N = toCheck.Length / 2;

        // Check strings of all lengths from 1 to N against the subsequent string of length 1 to N.
        for (int j=1; j<=N; j++)
        {
            // Check from beginning to j-1, compare against j to j+j.
            if (toCheck.Substring(0, j) == toCheck.Substring(j, j)) return true;
        }
    }

    return false;
}

Siéntase libre de hacer cualquier pregunta si no está claro por qué funciona.