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

Question

Моя проблема - найти повторяющуюся последовательность символов в данном массиве.просто, чтобы определить шаблон, в котором появляются символы.

<code>   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.
1: |<b> J </b>|<b> A </b>|<b> M </b>|<b> E </b>|<b> S </b>|<b> O </b>|<b> N </b>|<b> J </b>|<b> A </b>|<b> M </b>|<b> E </b>|<b> S </b>|<b> O </b>|<b> N </b>|
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'

<code>   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
2: |<b> R </b>|<b> O </b>|<b> N </b>|<b> R </b>|<b> O </b>|<b> N </b>|<b> R </b>|<b> O </b>|<b> N </b>|<b> R </b>|<b> O </b>|<b> N </b>|<b> R </b>|<b> O </b>|<b> N </b>|
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

<code>   .---.---.---.---.---.---.---.---.---.---.---.---.
3: |<b> S </b>|<b> H </b>|<b> A </b>|<b> M </b>|<b> I </b>|<b> L </b>|<b> S </b>|<b> H </b>|<b> A </b>|<b> M </b>|<b> I </b>|<b> L </b>|
   '---'---'---'---'---'---'---'---'---'---'---'---'

<code>   .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.
4: |<b> C </b>|<b> A </b>|<b> R </b>|<b> P </b>|<b> E </b>|<b> N </b>|<b> T </b>|<b> E </b>|<b> R </b>|<b> C </b>|<b> A </b>|<b> R </b>|<b> P </b>|<b> E </b>|<b> N </b>|<b> T </b>|<b> E </b>|<b> R </b>|
   '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'

---

Пример

Учитывая предыдущие данные, результат должен быть:

1. "JAMESON"
2. "RON"
3. "SHAMIL"
4. "CARPENTER"

---

Вопрос

• Как эффективно решить эту проблему?

Answer 1

Раствор языка (NlogN) * ​​1002 *

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

Answer 2

Для ваших примеров мой первый подход был бы следующим:

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

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

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

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

Answer 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:)

Answer 4

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

boolean findSubRepeating(String sub, String container);

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

Answer 5

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

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

Answer 6

Использование 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;

}

Answer 7

псевдокод

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

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

Answer 8

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

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

Не стесняйтесь задавать любые вопросы, если неясно, почему это работает.

Answer 9

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

с учетом последовательности 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)";
}

В основном:

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

Answer 10

Поместите всех ваших персонажей в массив 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, но это простое решение.