Записки программиста Программирование и не только

КМП поиск (Алгоритм Кнута Морриса Пратта)

Разъяснения напишу позже.

int Find (string str, string templ)
{
	int  i, j, strlen, templlen;

	strlen = str.length();
	templlen = templ.length();
	int *d = new int[templlen];
	// Вычисление префикс-функции
	i = 0;
	j = -1;
	d[0] = -1;
	while (i < templlen-1)
	{
		while ((j >= 0) && (templ[j] != templ[i]))
			j = d[j];
		++i;
		++j;
		d[i] = (templ[i] == templ[j]) ? d[j] : j;
	}
	// Поиск строки
	for (i = 0, j = 0; (i < = strlen-1) && (j <= templlen-1); ++i,++j)
		while ((j >= 0) && (templ[j] != str[i]))
			j = d[j];
	delete[] d;
	// Если совпадение есть - возвращаем позицию,
	// если нет - -1
	return (j == templlen) ? i - j : -1;
}

Вызывается:

	Find(*str, *tmpl)

Где:

	string* str;	//строка, в которой ищем
	string* tmpl;	//строка, которую ищем