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

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

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

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

Источник: Исследование за год или два по сопоставимой (тематической) теме.

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

Решение этой проблемы есть в Programming Pearls. Джон Бентли.

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

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

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

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

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

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]