0
I’m programming an exercise for my college and I have to do a String Matching code in KMP, so so far all right I did the whole code, tested some entries, when I went to test the teacher’s inputs there was a mistake, When I looked through the debug of my compiler it stops working after having passed all the lines, I’m like an idiot tried several things and it didn’t work and I don’t know what to do. Note: I am using the Eclipse C compiler.
The Code:
void stringMatchingKMP(char *texto, char *substring, int *prefixo, int tamTexto, int tamSub) {
int o = 1;
int s = 1;
int c = 1;
while (tamTexto - c > tamSub) {
while (s < tamSub && texto[o] == substring[s]) {
o++;
s++;
}
if (s >= tamSub) {
printf("%d ", c-1);
}
if (prefixo[s - 1] > 0) {
c = o - prefixo[s - 1];
} else {
if (o == c) {
o++;
}
c = o;
}
if (s > 1) {
s = prefixo[s - 1] + 1;
}
}
printf("\n");
}
int * funcaoPrefixo(char *substring, int tam) {
int * pref = (int *) calloc(tam + 1, sizeof(int));
pref[0] = 0;
pref[1] = 0;
pref[tam + 1] = 0;
int a = 0;
int b;
for (b = 2; b <= tam; b++) {
while (a > 0 && substring[a + 1] != substring[b]) {
a = pref[a];
}
if (substring[a + 1] == substring[b]) {
a = a + 1;
}
if (a < 0) {
pref[b] = a + 1;
} else {
pref[b] = a;
}
}
return pref;
}
int main() {
char texto[10002]="lorem ipsum dolor sit amet meis illum nec at summo cetero et usu adhuc justo tacimates cum et sint pericula mei eu pri ipsum eruditi periculis an no usu graecis explicari has animal sententiae in ut oportere suscipiantur mea ex est ullum quaestio in sit eius tibique no dolore numquam qui sed malorum persius utroque te ei sed omittam dissentias quaerendum ipsum altera vocent at cum facilisis iracundia sea ea mel tollit eripuit ex ne mei discere albucius sit tation convenire interesset at est te modus augue ei tempor assueverit eam ius causae definiebas at te wisi vituperata eos quem feugait vulputate mel et eum ut dicat ornatus pro cu prima deleniti patrioque ex mel ridens doctus mel consul volumus noluisse te mel oblique noluisse an te vis errem consulatu theophrastus est ne atomorum intellegam et mei scripta admodum has cu tollit primis essent exerci equidem vix te his ut sonet elaboraret qui at dicam epicurei et vel saepe instructior in soluta percipitur est quo reque voluptatum utfacilis tibique sapientem qui ut quo scripta voluptaria ad mea at possit nusquam mandamus duis facer legimus te sea id sale meis atqui nec scripta antiopam qui te nominavi mnesarchum incorrupte ut his qui ei putant impedit facilis partem nullam elaboraret vix id id probatus omittantur pro eum in ornatus repudiandae id qui alterum honestatis disputando errem graeco audiam vim ne";
int tamTexto = strlen(texto);
int t = 1;
while (t > 0) {
char substring[10] = "ipsum";
int tamSub = strlen(substring);
//ordenacao da substring
i = 0;
while (i <= tamSub) {
char aux = substring[tamSub - i];
substring[(tamSub + 1) - i] = aux;
i++;
}
substring[0] = ' ';
substring[tamSub + 1] = ' ';
//criação do vetor que acomodara a funcao prefixo
int * prefixo;
prefixo = funcaoPrefixo(substring, tamSub);
stringMatchingKMP(texto, substring, prefixo, tamTexto, tamSub);
t--;
}
exit(0);
return 0;
}
You said there was a mistake. What mistake?
– Jefferson Quesado
Arrived at the
exit
and left? That was the trouble?– Jefferson Quesado
I executed the code you posted, and except for not including
stdio.h
,stdlib.h
andstring.h
and not declaring the variablei
in functionmain()
, it works - although reporting the index a lower than it should (for example, returns5 118 356
for the code-mounted search, but should return6 119 357
)...– Wtrmute