Алгоритм Кнута-Морриса-Пратта или Рабина-Карпа (язык С++). Может у кого-нибудь есть готовый рабочий ?

[Беата]

пожалуйста

[Vago]

http://www.ics.uci.edu/~eppstein/161/kmp/
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

[Беата]

Сообщение от Vago

http://www.ics.uci.edu/~eppstein/161/kmp/
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

вообщем когда я ввожу его:

void preKmp(char *x, int m, int kmpNext[]) {
int i, j;

i = 0;
j = kmpNext[0] = -1;
while (i < m) {
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
i++;
j++;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}


void KMP(char *x, int m, char *y, int n) {
int i, j, kmpNext[XSIZE];

/* Preprocessing */
preKmp(x, m, kmpNext);

/* Searching */
i = j = 0;
while (j < n) {
while (i > -1 && x[i] != y[j])
i = kmpNext[i];
i++;
j++;
if (i >= m) {
OUTPUT(j - i);
i = kmpNext[i];
}
}
}


пишут, что идентификатор OUTPUT не найдени что "результатом вычисления фрагмента не является функция, принимающая 1 аргументов".. что делать?

[Vago]

Да это какая-то отладочная печать доморощенным макросом. Забейте этот оператор комментарием или вставьте печать стандартными ф-ями C / C++.

[Беата]

Сообщение от Vago

Да это какая-то отладочная печать доморощенным макросом. Забейте этот оператор комментарием или вставьте печать стандартными ф-ями C / C++.

можете мне помочь? у меня что-то ничего не получается

[Беата]

Сообщение от Vago

Да это какая-то отладочная печать доморощенным макросом. Забейте этот оператор комментарием или вставьте печать стандартными ф-ями C / C++.

можете мне помочь? у меня что-то ничего не получается

[Vago]

Господи, чему ж вас в ваших "высших школах" сейчас учат?!...

#include "stdio.h"
#include "string.h"

#define XSIZE 1024

/**
* Сразу за этим комментарием вставляете ф-ю preKmp без изменений.
*/


/**
 * Сразу за эти комментарием вставляете ф-ю KMP. Макрос OUTPUT(j - i); меняете на printf( "%d\n", j-i );
 */


void main() {

   char* czTheWholeString = "A roza upala na lapu";
   char* czStringToLookFor = "la";

   KMP( czStringToLookFor,
        strlen( czStringToLookFor ),
        czTheWholeString,
        strlen( czTheWholeString ) );

}

В качестве упражнения, можете добавить проверку на strlen( czTheWholeString ) <= XSIZE и красивую печать.

Added 21:00 CET
Или ничего не меняете и в KMP тоже, а после строчки с #define добавляете ещё одну:

#define OUTPUT( arg ) printf( "%d\n", arg );

Но этим Вы, наверняка, дадите Вашему преподавателю повод задать Вам пару дополнительных вопросов. Не уверен пока, что Вам этого хочется.

[Беата]

Сообщение от Vago

Господи, чему ж вас в ваших "высших школах" сейчас учат?!...

сложный вопрос..