Строки C++: поиск подстроки методом Кнута-Морриса-Пратта

Ну что замучились искать алгоритмы поиска подстроки? Привожу метод, который РАБОТАЕТ! Сам пробовал 🙂

int find_substring(char s[], char q[]){
	int i, j, N, M;
	N = strlen(s);
	M = strlen(q);
	int *d =(int*)malloc(M*sizeof(int)); /* динамический массив длины М*/
	/* Вычисление префикс-функции */
	i=0;
	j=-1;
	d[0]=-1;
	while(i=0) && (q[j]!=q[i]))
			j = d[j];
		i++;
		j++;
		if(q[i]==q[j])
			d[i]=d[j];
		else
			d[i]= j;
	}
	/* поиск */
	for(i=0,j=0;(i=0)&&(q[j]!=s[i]))
			j=d[j];
	free (d); /* освобождение памяти массива d */
	if (j==M)
		return i-j;
	else /* i==N */
		return -1;
}

Kamo Petrosyan Автор

Комментарии

    xaker1

    (Июнь 22, 2013 - 7:14 пп)

    код нерабочий — явно около while потеряна открывающая фигурная скобка {

Добавить комментарий

Ваш e-mail не будет опубликован.