Поиск повторений
Есть строка (не строка, а по идее sampleData аудио файла), вот я в ней хочу найти повторения. Выгуглил только поиск известных подстрок, а в данном случае мы их не знаем.
Пример: аллаелапомидорыалаеламидий На выходе(подстрока и список адресов подстроки): аллаела - 0,15 мид-9,22 ... ... Т.е ищем максимальные по длине подстроки. Чую сам не догоню |
Ответ: Поиск повторений
Напишу на пурике - но общий алгоритм думаю понятен. Фиг знает как с производительностью...:)
Наверно нужно ограничение на длину семпла... Код:
data.s=... ;Исходные данные |
Ответ: Поиск повторений
Точно, можно же найти первый подсемпл и потом стандартным алгоритмом его прогнать и найти все вхождения , что-то затупил:)
А можно, я так подумал, АКФ расчитать и в пиках функции буду совпадения. http://ru.m.wikipedia.org/wiki/%D0%9...%D0%B8%D1%8 F Эта штука хороша для аудиоигр, что бы не только в зависимости от спектра была игра |
Ответ: Поиск повторений
Но если по теме еще нужно, то самый оптимальный алгоритм описан тут
http://e-maxx.ru/algo/string_tandems Вообще на этом сайте собрано много различных алгоритмов из разных областей, используемых во основном на олимпиадном программировании, там где важна скорость выполнения. Но предупреждаю что алгоритм далеко не простой, задача не тривиальна. Хотя для других задач есть удивительно простые но в тоже время удивительно быстрые алгоритмы. Вообщем советую сайт:) ИСПРАВЛЕНО: извиняюсь ошибся, по ссылке немного другая задача. Но можешь вообще по сайту посмотреть, может что полезное будет, благо со строками там не мало алгоритмов |
Часовой пояс GMT +4, время: 16:17. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot