Искать повтор (любой тип повторения) подстроки в длинной строке без пробела

Question

Я задал тот же вопрос раньше, но не получил то, что хочу. Так что придется публиковать его снова.

У меня очень длинная строка, в которой нет места. Теперь я пытаюсь найти повторяющуюся подстроку (любой тип, без определенного шаблона) в этой длинной строке. Длина повторения может быть диапазоном между (min, max), т. Е. (Min = 3. max = 5).

Например: Строка s = "atggucttuaccccggucttaacccc"; , в котором «gguctt» и «acccc» являются двумя разными повторяющимися подстроками (я не знаю этого, прежде чем запускать код).

Итак, я блуждаю по C#, есть ли какой-нибудь быстрый способ определить повторы и место, где происходят повторы?

Заранее спасибо.

Answer 1

Вы, по сути, ищете поиск строки для подстроки, но подстроки состоят из всех возможных подстрок в строке.

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

Для каждого размера куска я буду перебирать строку, беря куски соответствующего размера и используя алгоритм сопоставления строк, такой как Boyer-Moore (или встроенный алгоритм поиска строк), чтобы увидеть, повторяется ли строка. Обратите внимание, что нужно искать только оставшуюся часть строки, если в строке было повторение, было бы сопоставлено то, что этот регион был куском. Вы также можете ограничить область поиска, чтобы исключить последние строки (chunk_size - 1) в строке, поскольку совпадение не может начаться после этого (хотя ваш алгоритм поиска строк может сделать это для вас). Я бы также сохранил хэш-таблицу всех уже проверенных кусков, чтобы избежать необходимости повторять их снова, это было бы особенно важно для первых нескольких итераций, где размер куска мал.

В псевдокоде:

match_min = 2 
match_max = 5 

search_cache = Hashtable() 
for (chunk_size = match_min; chunk_size < min(match_max+1, len(str)/2); chunk_size++){ 
    for (start = 0; start < len(str) - chunk_size; start++){ 
    sub = str.substring(start, start + chunk_size) 
    // We want to know if sub repeats 
    if (sub not in search_cache) 
     search_cache[sub] = str.substring(start + chunk_size, len(str) - chunk_size + 1).find(sub) 
    if (search_cache[sub] != -1) 
     print "MATCH FOUND %s at %d-%d" % (sub, start, search_cache[sub]) 
    } 
} 

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

Эффективность этого будет примерно равна O (c * m * n), где c - константа, представляющая эффективность вашего алгоритма поиска строки (амортизированная стоимость выполнения строкового поиска), m - размер строки , а n - (max - min). Это также функция количества повторений в строке, как если бы энтропия была низкой, search_cache сэкономил бы вам больше времени. Приближение c как O (n) делает функцию примерно O (n^2).

Answer 2

Попробуйте это:

var matches = Regex.Matches("atggucttuaccccggucttaacccc", @"((.)\2+)") 

Это даст вам позиции матчей тоже. Дополнительная информация here.

EDIT: Только что поняли, что вам нужно выполнить произвольное повторное сопоставление строк, а не только повторение символьного символа.

Answer 3

Если длина длинная, вы можете посмотреть в Suffixtrees или Suffixarrays. Они эффективно решают эту и подобные проблемы.