forum.boolean.name - Поиск повторений

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Поиск повторений (http://forum.boolean.name/showthread.php?t=19358)

Поиск повторений

Есть строка (не строка, а по идее sampleData аудио файла), вот я в ней хочу найти повторения. Выгуглил только поиск известных подстрок, а в данном случае мы их не знаем.
Пример:
аллаелапомидорыалаеламидий
На выходе(подстрока и список адресов подстроки):
аллаела - 0,15
мид-9,22
...
...
Т.е ищем максимальные по длине подстроки.

Чую сам не догоню

Ответ: Поиск повторений

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

Код:

data.s=... ;Исходные данные

max_sample.i=10 ;Ограничение на длину семпла

Structure sample

  List Pos.i()

EndStructure

NewMap Samples.Sample()



;Перебираем все символы - позиция "курсора"

For pos=1 To Len(data)



  ;Перебираем семплы разной длины от данной позиции

  For sample_len=1 to max_sample

    cur_sample.s=Mid(data,pos,sample_len)



    ;Ищем данный семпл в сохраненных

    If FindMapElement(Samples(),cur_sample)=0



      ;Если нет, добавляем

      AddMapElement(Samples(),cur_sample)



      ;Ищем данный семпл в оставшейся части данных, запоминаем позиции

      find_pos=FindString(data,cur_sample,pos)



      Repeat

        AddElement(Samples()\Pos())

        Samples()\Pos()=find_pos

        find_pos=find_pos+Len(cur_sample)

        find_pos=FindString(data,cur_sample,find_pos)

      Until find_pos>0



    EndIf



  Next



Next

В итоге получим кучу записей Samples() со списком позиций в каждой.

Ответ: Поиск повторений

Точно, можно же найти первый подсемпл и потом стандартным алгоритмом его прогнать и найти все вхождения , что-то затупил:)

А можно, я так подумал, АКФ расчитать и в пиках функции буду совпадения.
http://ru.m.wikipedia.org/wiki/%D0%9...%D0%B8%D1%8 F

Эта штука хороша для аудиоигр, что бы не только в зависимости от спектра была игра

Ответ: Поиск повторений

Но если по теме еще нужно, то самый оптимальный алгоритм описан тут
http://e-maxx.ru/algo/string_tandems
Вообще на этом сайте собрано много различных алгоритмов из разных областей, используемых во основном на олимпиадном программировании, там где важна скорость выполнения.
Но предупреждаю что алгоритм далеко не простой, задача не тривиальна.
Хотя для других задач есть удивительно простые но в тоже время удивительно быстрые алгоритмы. Вообщем советую сайт:)

ИСПРАВЛЕНО: извиняюсь ошибся, по ссылке немного другая задача.
Но можешь вообще по сайту посмотреть, может что полезное будет, благо со строками там не мало алгоритмов