int seek_substring_A (char s[], char q[]){
	int i, j, k, N, M;
	N = strlen(s);
	M = strlen(q);
	k = -1;
		do {
		k++; /* k - смещение шаблона по строке */
		j = 0; /* j - смещение по шаблону; */
		while ((j<M) && s[k+j]==q[j]))
			j++;
		if (j == M)
			return k; /* шаблон найден */
		} while (k < N - M );

	return -1; /* шаблон не найден */
}

Алгоритм Бойера-Мура

Данный алгоритм ведет сравнение символов из строки и шаблона, начиная с q[М – 1] и с s[i + М – 1] элементов в обратном порядке.

В нем используется дополнительная таблица сдвигов d. Для каждого символа x из алфавита (кроме последнего в шаблоне) d есть расстояние от самого правого вхождения х в шаблоне до последнего символа шаблона. Для последнего символа в шаблоне d равно расстоянию от предпоследнего вхождения х до последнего или М, если предпоследнего вхождения нет.

Пример построения таблицы сдвигов

Для шаблона “аbсаbеаbсе” (М = 10)

a d['a'] = 3,

b d['b'] = 2,

d d['c'] = 1,

e d['e'] = 4 (!предпоследнее вхождение)

и для всех символов х алфавита, не входящих в шаблон,

d[x] = 10.

Алгоритм:

Будем последовательно сравнивать шаблон q с подстроками

s[i – М + 1..i] (в начале i = М).

Введем два рабочих индекса: **j** = М, М – 1, ... , 1 — пробегающий символы шаблона **k** = i, ... ,i – M+1 — пробегающий подстроку.

Оба индекса синхронно уменьшаются на каждом шаге.