Как найти повторяющуюся последовательность символов в заданном массиве?

Ответ 1

Для ваших примеров первым моим подходом было бы

• получить первый символ массива (для вашего последнего примера это будет C)
• получить индекс следующего появления этого символа в массиве (например, 9)
• если он найден, найдите следующий вид подстроки между двумя появлениями символа (в этом случае CARPENTER)
• если он найден, вы закончили (и результат - это подстрока).

Конечно, это работает только для очень ограниченного подмножества возможных массивов, где одно и то же слово повторяется снова и снова, начиная с самого начала, без случайных символов между ними, и его первый символ не повторяется внутри слова, Но все ваши примеры попадают в эту категорию - и я предпочитаю самое простое решение, которое могло бы работать: -)

Если повторяющееся слово содержит первый символ несколько раз (например, CACTUS), алгоритм может быть расширен, чтобы искать последующие вхождения этого символа, а не только первый (чтобы он нашел полное повторяющееся слово, не только подстрокой его).

Обратите внимание, что этот расширенный алгоритм даст другой результат для вашего второго примера, а именно RONRON вместо RON.

Ответ 2

Решение по языку O (NlogN)

Выполнение БПФ на вашей строке (обработка символов как числовых значений). Каждый пик в полученном графе соответствует периодичности подстроки.

Ответ 3

В Python вы можете использовать регулярные выражения таким образом:

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'

Я не уверен, как это переводится на Java или C. (Это одна из причин, по которой мне нравится Python.: -)

Ответ 4

Сначала напишите метод, который находит повторяющуюся подстроку sub в строке контейнера, как показано ниже.

boolean findSubRepeating(String sub, String container);

Теперь продолжайте вызывать этот метод с увеличением подстроки в контейнере, сначала попробуйте 1 символьную подстроку, затем 2 символа и т.д. вверх до container.length/2.

Ответ 5

Псевдокод

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

Примечание. Для краткости я изобретаю метод "повторения" для строк, который на самом деле не является частью строки Java; "ABC".repeat(2) = "abcabc"

Ответ 6

Использование С++:

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

}

Ответ 7

Первая мысль, которая приходит мне на ум, - это попытка повторить последовательности длин, которые делят длину (S) = N. Существует максимум N/2 таких длин, поэтому это приводит к алгоритму O (N ^ 2).

Но я уверен, что его можно улучшить...

Ответ 8

и вот конкретный рабочий пример:

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

Ответ 9

Я бы преобразовал массив в объект String и использовал regex

Ответ 10

Не знаете, как вы определяете "эффективно". Для простой/быстрой реализации вы можете сделать это в Java:

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

он пытается найти кратчайшую строку (.+?), которая должна повторяться как минимум один раз (\1+), чтобы соответствовать всему входному тексту.

Ответ 11

Поместите весь свой символ в массив e.x. а []

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

Тогда отношение (i/j) = количество повторов в вашем массиве. Вы должны обратить внимание на пределы i и j, но это простое решение.

Ответ 12

Вот более общее решение проблемы, которое найдет повторяющиеся подпоследовательности в последовательности (чего-либо), где подпоследовательности не должны начинаться в начале и не сразу следовать друг за другом.

задана последовательность b [0..n], содержащая данные, о которых идет речь, а порог t - минимальная длина подпоследовательности, чтобы найти,

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

В основном:

• Начните с начала данных, итерации до тех пор, пока не достигните 2 * t конца (нет возможного способа иметь две различные подпоследовательности длины t менее чем за 2 * т пространства!)
• Для второй подпоследовательности запустите, по крайней мере, t байт, где начинается первая последовательность.
• Затем reset длина обнаруженной подпоследовательности до 0 и проверьте, есть ли у вас общий символ в я + l и j + l. Пока вы делаете, увеличивайте l. Когда у вас больше нет общего характера, вы достигли конца вашей общей подпоследовательности. Если подпоследовательность больше порога, напечатайте результат.