Длина двоичной последовательности "A" - m символов.
Длина двоичной последовательности "B" - n символов.

Известно, что m гораздо меньше n (т.е. на грани сравнимости, ну, например, 10^6<n/m<10^7).
Сколько раз встречается последовательность A в последовательности B? 

Можно сделать так:
1. Сделать логическое И последовательности А и B (A & B)
2. Проверить на равенство результата коньюнкции с B (Результат == B)
    Если равно то увеличить счетчик на 1
3. Сделать логический сдвиг вправа последовательности B на 1 шаг (B << 1)
4. Перейти к шагу 1, если мы не вышли за граници
 

Для ускорения поиска можно сдвигать не на один бит а на определенные заранее К бит.

Для этого надо найти в посл-ти А максимальную подпоследовательность начинающуюся с начала и равную подпоследовательности той же длины на которую заканчивается А.
То есть
если А = 110110, то надо сдвигать на 3 символа за каждое сравнение, 
если например А = 100001, то можно сдвигать на 5 символов,
а если А = 111111, то придется сдвигать на 1 символ...

 

http://algolist.manual.ru/search/index.php 

Предположим, что А=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 бит, при совпадении на несколько. Но есть "но". Будет хорошо если последовательность А заранее известна, и можно заранее определить кол-во сдвиговых бит. А если она не определена заранее, то определение длины максимально длиного сдвига, может занять дольше времени, чем проверка с малым сдвигом.


 

Составляешь конечный автомат по искомой последовательности и ищешь. Сложность- линейная. 

Простите, линейная от чего:?

 

Ну так сколько раз? Формула бывает? 

Вобщем-то это я и имел в виду, только как-то написал не так... :-)



Я думаю, что при условии
"Известно, что m гораздо меньше n (т.е. на грани сравнимости, ну, например, 10^6<n/m<10^7)."
(Описано автором) эта оптимизация может очень даже пригодиться. 

Кстати всю строку Б каждый раз сравнивать не обязательно. Например для 8битного сравнения достаточно сравнивать по одному байту,
до тех пор пока совпадают. Как только обнаружили разницу, дальше проверять не имеет смысла, поетому сдвигаем цепочку на один байт и начинаем заново побайтово проверять цепочку Б.

П.С. Надеюсь я понятно выразился, если нет попытаюсь заново.  

Это сообщение отредактировал(а) mes - 2.5.2006, 23:48

От входной длины. Только нужен не обыкновенный автомат, а машина Тьюринга. Тк у простого КА нет памяти. 

Такой не знаю. Могу предположить, что это КА с памятью 
Просто счетчик, и чего мудрить? 

Вообщем то так и есть. У классического КА нет памяти. Либо семмантики навешивать, те юзать счетчик в нужном состоянии. 

Можно использовать КА со стеком, из которого не будем ничего убирать, а приписывать только единицы.
Вроде, задачу решили.