Самая длинная неперекрывающаяся подстрока

Question

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

Например, в строке

ABADZEDGBADEZ

самый длинный повторяющийся будет "ПЛОХО". Кстати, если такого результата нет, алгоритм должен предупредить, что такая вещь произошла. Я предполагаю, что это связано с деревьями суффиксов.

Я уверен, что это должно уже где-то существовать. Спасибо за помощь!

Answer 1

Поскольку вы применяете это к музыке, вы, вероятно, не ищете 100% совпадений; будут ожидаемые различия от одного экземпляра темы к другому. Вы можете попробовать поискать алгоритмы анализа последовательности генов - там происходит множество всего этого. Попробуйте BLAST или другие алгоритмы выравнивания.

Вы также можете попробовать семейство алгоритмов WinEPI, а также различные реализации дерева префиксов этого конкретного набора результатов (эти результаты допускают пробелы в подстроке; например, ABCID и AFBCD оба содержат ABCD). На самом деле у меня есть статья об алгоритме, на которую стоит взглянуть, если вам будет интересно; Мне нужно получить разрешение на распространение, поэтому дайте мне знать.

Обратите внимание, что на самом деле это ОЧЕНЬ сложная тема (для эффективного выполнения) для больших наборов данных.

Источник: Исследования в течение года или двух по сопоставимой теме (определение темы).

Answer 2

Суффиксный массив - хорошая структура данных для решения этой проблемы.

Есть решение этой проблемы в Программировании Жемчуга Джоном Бентли.

Answer 3

Простой алгоритм состоит в том, чтобы сделать это:

• Создать структуру данных, представляющую фрагменты строки; реализовать сравнение / сортировку в зависимости от языка
• Создайте список каждого фрагмента строки, начиная с [первый символ, последний символ], [второй символ, последний символ], до [последний символ, последний символ]
• Сортировать этот список - O(n log n)
• Это объединяет все строковые фрагменты с общими префиксами. Затем вы можете выполнить итерацию по списку, сравнивая каждую пару, чтобы увидеть, сколько символов они разделяют в начале, и, если он больше вашего максимума, запишите его и установите в качестве нового максимума.

(Как указано в другом ответе, я описываю массив суффиксов здесь.)

Answer 4

Хорошо, вот одна безумная идея.

Создайте функцию, которая определяет, существует ли повторяющаяся подстрока длины k в O(n) (где n - длина текста). Это можно сделать, используя скользящий хеш (см. Википедию Алгоритм согласования строк Рабина-Карпа), чтобы сгенерировать все n хешей за линейное время, и использовать хеш-таблицу /BST (или карту, или dict, или как называется ваш язык) для хранения соответствующие позиции подстроки. Прежде чем вставить текущий хеш в структуру данных, мы проверяем, видели ли мы его раньше. Если это было замечено ранее, мы просто ищем индексы, где был создан этот хеш, и видим, является ли соответствующая подстрока неперекрывающимся соответствием.

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

Код в Python следует

A=23
MOD=10007 # use a random value in the real world

def hsh(text):
    return sum([ord(c)*A**(len(text)-i-1) for i,c in enumerate(text)])%MOD

def k_substring(text, k):
    substrings={}
    cur=hsh(text[:k])
    pwr=(A**(k-1))%MOD
    substrings[cur]=[0]
    for i in xrange(k,len(text)):
        to_remove=(ord(text[i-k])*pwr)%MOD
        to_add=ord(text[i])
        cur-=to_remove
        if cur<0:
            cur+=MOD
        cur=(cur*A)%MOD
        cur=(cur+to_add)%MOD
        if cur in substrings:
            lst=substrings[cur]
            for index in lst:
                if index+k<=i-k+1 and text[index:index+k]==text[i-k+1:i+1]:
                    return index
            lst.append(i-k+1)
        else:
            substrings[cur]=[i-k+1]
    return -1

def longest_substring(text):
    hi,lo=len(text),0
    while hi>lo:
        mid=(hi+lo+1)>>1
        if k_substring(text,mid)==-1:
            hi=mid-1
        else:
            lo=mid
    index=k_substring(text,lo)
    return text[index:index+lo]

(Извините, если это неясно. Сейчас 6:30 утра, и мне действительно нужно вернуться в постель:))