Прямий пошук рядка в тексті

Часто доводиться зіштовхуватися зі специфічним пошуком, так названим пошуком рядка в тексті. Його можна визначити таким способом.

Нехай заданий масив 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*М порівнянь.