
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.97.9.174] |
![]() |
|
Сообщ.
#1
,
|
|
|
нужно сравнить 2 массива, найти в них одинаковые куски, причем куски могут быть разной длины и в разных частях массива, их может быть разное количество т.е.
1 2 A M B N C A X B X C S Y должны найтись куски ABC, их смещения в файлах мне приходит в голову только самый простой перебор, вот только на каждый байт одного массива надо просмотреть другой, а это долго уже при 1mb... |
Сообщ.
#2
,
|
|
|
Можно попробовать так:
1) Сначала составляешь массивы остатков a[1] = "ABCXXS" a[2] = "BCXXS" a[3] = "CXXS" a[4] = "XXS" a[5] = "XS" a[6] = "S" b[1] = "MNABCY" b[2] = "NABCY" b[3] = "ABCY" b[4] = "BCY" b[5] = "CY" b[6] = "Y" Разумеется не физически (а то много памяти займет), а всего два массива указателей делаешь a[] и b[]. (O(N) - операций) 2) Потом каждый их них сортируешь по алфавиту (O(N*log(N)) - операций) (Перетасовываешь указатели) 3) Ищешь похожие элементы в двух УПОРЯДОЧЕННЫХ массивах. a[1] похож на b[3] в первых 3 символах... a[2] like b[4] -> 2 a[3] like b[5] -> 1 Сложность = O(N*Log(N) + N*g*c), где g - сложность сравнения двух строк, c- коэффициент количества похожих строк 0 < c < 100\% |
Сообщ.
#3
,
|
|
|
Если немного переделать алгоритм Кнута-Мориса-Пратта, то получится как раз решение задачи.
|
Сообщ.
#4
,
|
|
|
А что за алгоритм Кнута-Морриса?
|
Сообщ.
#5
,
|
|
|
хехе делал я нечто подобное, и даже дока была крутейшая, правда на наглийском...
если тебенадо точно, то полный перебор (правда это будет долго) если надо быстрее, то все решается хеш таблицей за 1, или полтора прохода по каждому из массивов (в моем случае это были 200 мб файлы) но при этом ессно будут найдены не все одинаковые куски.... |
Сообщ.
#6
,
|
|
|
Цитата AGAMEMNUM, 03.12.02, 16:35:26 А что за алгоритм Кнута-Морриса? http://algolist.manual.ru/search/esearch/kmp.php ;D ;D ;D |
Сообщ.
#7
,
|
|
|
В свое время использовал циклический проход одного массива по другому. Т.е. производим сдвиг элементов массива В влево или вправо. И производим сравнение всех элементов обоих массивов. Общее количество операций n2, n - размер массивов
|