Цитата(Breed @ 27.4.2006, 05:56  ) |
| Для ускорения поиска можно сдвигать не на один бит а на определенные заранее К бит. Для этого надо найти в посл-ти А максимальную подпоследовательность начинающуюся с начала и равную подпоследовательности той же длины на которую заканчивается А. То есть если А = 110110, то надо сдвигать на 3 символа за каждое сравнение, |
Предположим, что А=110110 последовательность В = 11101100000,
Если мы будем сдвигать по три бита, то получим следующие варианты цепочки В:
1. 111011 (00000) - в скобках остаток цепочки В, который длиней А.
2. 011000 (00)
3. 00000
Т.е ни одного совпадения.
Давайте проверим если будем сдвигать на один бит:
1. 111011(00000)
2. 110110(0000) -! Совпадение.
3. 101100(000)
4. 011000(00)
5. 110000(0)
6. 100000
Как видим два варианта дают различный вариант, а значит один из них не верный. Конечно есть третий вариант - при неудачном сравнении сдвигать на 1 бит, при совпадении на несколько. Но есть "но". Будет хорошо если последовательность А заранее известна, и можно заранее определить кол-во сдвиговых бит. А если она не определена заранее, то определение длины максимально длиного сдвига, может занять дольше времени, чем проверка с малым сдвигом.
