Задача состоит в следующем: у нас есть очень длинная исходная строка, и значительно более короткая подстрока. Алфавит достаточно маленький, 5-6 символов. Подскажите наиболее быстрый алгоритм поиска, и как возможно вообще ускорить поиск? Что можете посоветовать? Меня интересует именно сравнение скорости работы алгоритмов, какой вы считаете более продуктивным по СКОРОСТИ.

Если "буквы алфавита" встречаются с равной частотой, то честно говоря, не представляю себе ничего, кроме последовательного прохода всех положений от начала строки до конца (минус длина подстроки, конечно).

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

1. Можно тупо сравнивать символы. Тогда придется сравнивать 8-битные буквы. Это не так глупо, так как в большинстве языков сравнение символов уже оптимизировано.

2. Поскольку символов всего 6, 8-битного представления не нужно. Достаточно 3-битного. Если можно написать оптимизированную процедуру сравнения 3-битных символов, скорее всего будет быстрее.

3. Перевести обе строки в биты и сравнивать побитно. Опять же, при прочих равных, такое сравнение будет наиболее быстрым. Однако, в этом случае надо будет учесть-отбросить редкие случаисовпадения со сдвигом; т.е. случаи когда битовая последовательность совпала, но не с начала буквы, а откуда-то с середины. Впрочем, даже простая проверка в символьной форме много времени на займет по сравнению со временем прохода.

______________

Теперь, если частотность букв не одинакова. Например, есть у нас в подстроке Ъ - редко встречающийся символ. Тогда быстрее всего будет искать в строке этот символ, а потом просто сравнивать "хвосты" в обе стороны.

Эту идею можно развить и дальше. Искать самый редкий символ, потом смотреть есть ли на должном расстоянии от него второй по невстречаемости и так далее. Но большой ли это даст выигрыш - не скажу сразу.

______________


Если я недостаточно подробно расписал - требуйте пояснений  

Разветвлённая теория есть на эту тему.

Наверное, это Вы хотели:
Тут можете посмотреть сравнение алгоритмов поиска подстроки в строке

Есть ещё алгоритмы поиска массива подстрок (например, алгоритм Ахо-Корасик)

Посмотрите алгоритмы типа Хорспула, Бойера-Мура или Кнута-Морриса-Пратта, и прикиньте, дают ли они существенный выигрыш при ваших конкретных условиях.

Наверное кроме вопроса ТС-у стоило разместить ссылку на Хабр? Вдруг кого-то тоже заинтеерсует возможность выиграть 1 из Asus Zenbook UX31E