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

30Мар/103

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

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

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;	//строка, которую ищем
Метки записи: , 3 Комментарии
30Мар/100

Быстрая сортировка (Pascal)

В дополнении к ЭТОЙ теме.

procedure quickSort(l,h: integer);
var
	i,j,mid,tmp: integer;
begin
	i := l;
	j := h;
	mid := mArray[(l + h) div 2];
	repeat
		while mArray[i] < mid do inc(i);
		while mArray[j] > mid do dec(j);
		if (i < = j) then
		begin
			if (i < j) then
			begin
				tmp := mArray[i];
				mArray[i] := mArray[j];
				mArray[j] := tmp;
			end;
			inc(i);
			dec(j);
		end;
	until i > j;
	if l < j then quickSort(l, j);
	if i < h then quickSort(i, h);
end;