FilesExpand file tree

master

/

KMP.c

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (49 loc) · 968 Bytes

master

/

KMP.c

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (49 loc) · 968 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

#include<stdio.h>

#include<malloc.h>

#include<string.h>

#define NOT_FOUND -1;

void KMPnext(char *substr, int *next);

int KMP(char *str, char *substr);

int KMP(char *str, char *substr){

int *next;

int i = 0;

int j = 0;

//abcdefabcdefgabcdefgabcd

//bcdefg

next = (int *)calloc(sizeof(int), strlen(substr));

KMPnext(substr, next);

while(str[i]){

for(j = next[j]; substr[j] && str[i] == substr[j]; i++, j++){

;

}

if(substr[j] == 0){

return i-j;

}

if(j == 0){

i++;

}

}

free(next);

return NOT_FOUND;

}

void KMPnext(char *substr, int *next){

int index;

int j;

for(index = 2; substr[index]; index++){

for(j = index-1; j && substr[next[j]] != substr[index-1]; j = next[j]){

;

}

next[index] = j ? next[j]+1 : 0;

}

}

void main(void){

char substr[80] = {0};

char str[80] = {0};

int index;

printf("str : ");

scanf("%s", str);

printf("substr : ");

scanf("%s", substr);

index = KMP(str, substr);

printf("%d\n", index);

}