Comment trouver la séquence répétitive de caractères dans un tableau donné?

solution de langue dans la joue O(NlogN)

effectuer un FFT sur votre chaîne (en traitant les caractères comme des valeurs numériques). Chaque pic du graphique qui en résulte correspond à une périodicité de substrat.

en Python, vous pouvez utiliser regexes ainsi:

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

recurrence('abcabc') # Returns 'abc'

Je ne suis pas sûr que cela se traduise en Java ou C. (C'est une des raisons pour lesquelles J'aime Python, je suppose. : -)

Ecrivez D'abord une méthode qui trouve la répétition du substrat sub dans la chaîne du conteneur comme ci-dessous.

boolean findSubRepeating(String sub, String container);

maintenant, continuez à appeler cette méthode avec augmentation de la sous-chaîne dans le conteneur, d'abord essayer une sous-chaîne de 1 caractère, puis 2 caractères, etc allant jusqu'à container.length/2.

Pseudo

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)
      }
   }
}

Note: pour être bref, j'invente une méthode "repeat" pour les chaînes, qui ne fait pas réellement partie de la chaîne de Java; "abc".répétez les étapes(2)="abcabc"

Utiliser 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 première idée qui me vient à l'esprit est d'essayer toutes les séquences répétitives de longueurs qui divisent longueur(S) = N. Il y a un maximum de n/2 de telles longueurs, donc cela aboutit à un algorithme O(N^2).

Mais je suis sûr qu'il peut être amélioré...

et voici un exemple concret de travail:

/* 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++);

Je convertirais le tableau en un objet String et j'utiliserais regex

Je ne sais pas comment vous définissez "efficacement". Pour une implémentation facile / rapide, vous pouvez le faire 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;
    }

il essaie de trouver la plus courte chaîne (.+?) qui doit être répété au moins une fois (+) pour correspondre au texte d'entrée entier.

mettez tout votre personnage dans un tableau E. x. a []

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

alors le rapport de (i/j) = compte de répétition dans votre tableau. Vous devez faire attention aux limites de i et j, mais c'est la solution la plus simple.

Voici une solution plus générale au problème, qui trouvera des repeating subsequences dans une séquence (de n'importe quoi), où les subsequences ne doivent pas commencer au début, ni immédiatement suivre l'autre.

étant donné une séquence b[0..n], contenant les données en question, et un seuil t étant la longueur minimale de la suite à trouver,

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)";
}

en gros:

1. commencer au début des données, itérer jusqu'à 2*t près de la fin (il n'est pas possible d'avoir deux suites distinctes de longueur t en moins de 2*t d'espace!)
2. pour la deuxième suite, commencez au moins t octets au-delà de l'endroit où la première séquence commence.
3. puis, réinitialisez la longueur de la subsequence découverte à 0, et vérifiez si vous avez un caractère commun à i+l et j+L. Aussi longtemps que vous le faites, increment l. Lorsque vous n'avez plus un caractère commun, vous avez atteint la fin de votre commune sous-suite. Si le sous-suite est plus que votre seuil, imprimer le résultat.

J'ai trouvé moi-même et j'ai écrit un code pour ça (écrit en C#) avec beaucoup de commentaires. Espérons que cela aide quelqu'un:

// 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;
}

N'hésitez pas à poser des questions si vous ne savez pas pourquoi cela fonctionne.