blob: f74dcf0742e6778569994d58a01535ddf5a31f1c (
plain)
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
60
61
62
63
64
65
66
67
68
69
70
|
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "kmp.h"
/* KMP implementation stolen from Github user cagdass*/
int* init_array(int size) {
int* arr = (int*)malloc(size * sizeof(int));
int i;
for(i = 0; i < size; i++) {
arr[i] = 0;
}
return arr;
}
int kmp(const char* t,size_t tlen, const char* p,size_t plen) {
int m = plen;
int n = tlen;
int* f = init_array(m); // Failure function values.
int i = 0;
int j = 0;
while (i < n) {
if (t[i] == p[j]) {
if (j == m - 1) {
return i - j;
}
else {
i += 1;
j += 1;
}
}
else {
if (j > 0) {
j = f[j-1];
}
else {
i += 1;
}
}
}
return -1;
}
void failure(const char* p, int* f) {
f[0] = 0;
int i = 1;
int j = 0;
int m = strlen(p);
while (i < m) {
if (p[i] == p[j]) {
f[i] = j + 1; // j+1 matches up to the current character.
i += 1;
j += 1;
}
else if (j > 0) {
j = f[j - 1];
}
else {
f[i] = 0;
i += 1;
}
}
}
|
