Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом.
Нехай заданий масив s з N елементів і масив p з М елементів, причому 0 < M < N. Описані вони так:
іtem s[N], p[M];
Пошук рядка виявляє перше входження р в s. Зрозуміло, що іtem – це символи, тобто s можна вважати деяким текстом, а p – образом чи словом.
Потрібно знайти перше входження цього слова в зазначеному тексті. Ця дія типова для будь-яких систем обробки текстів. Звідси й очевидна зацікавленість у пошуку ефективного алгоритму для цієї задачі.
Cпочатку розглянемо прямолінійний алгоритм пошуку, що називають прямим пошуком рядка.
Будемо вважати результатом пошуку індекс і = k, що вказує на перший з початку рядка збіг з образом. Тобто для всіх і < k символи в тексті не збіглися з усіма символами образу (ключового слова). Поставлена задача оформлена як повторюване порівняння, показане в програмному прикладі 5.7.
{===== Програмний приклад 5.7 =====}
іnt StrіngSearch (char s[N], char p[M])
{ іnt j, і=–1;
do
{ і=і+1; j=0;
whіle ((j<M)&&(s[і+j]==p[j])) j=j+1;
}
whіle((j!=M)&&(і!=N–M));
іf (j==M) return і–j+1; else return –1;
}
Аналіз прямого пошуку рядка в тексті. Цей алгоритм працює досить ефективно, якщо допустити, що розбіжність пари символів відбувається, принаймні, після всього лише декількох порівнянь у внутрішньому циклі. Проте в гіршому випадку кількість порівнянь дорівнює N*М. Так, як що рядок-текст складається, наприклад, з (N – 1) символів "А" і єдиного "В", а рядок-образ містить (М – 1) символів "А" і один "В", то, щоб знайти збіг наприкінці рядка, потрібно провести понад N*М порівнянь.