-
Notifications
You must be signed in to change notification settings - Fork 30
/
test_kmp.c
77 lines (67 loc) · 1.77 KB
/
test_kmp.c
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
71
72
73
74
75
76
77
#include "kmp.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "alloc-testing.h"
#include "test_helper.h"
extern int *kmp_calculate_next(const char *string, int len);
void test_kmp_calculate_next()
{
int *next;
next = kmp_calculate_next("abc", 3);
assert(next[0] == 0);
assert(next[1] == 0);
assert(next[2] == 0);
free(next);
next = kmp_calculate_next("aaa", 3);
assert(next[0] == 0);
assert(next[1] == 1);
assert(next[2] == 2);
free(next);
next = kmp_calculate_next("abababab", 8);
assert(next[0] == 0);
assert(next[1] == 0);
assert(next[2] == 1);
assert(next[3] == 2);
assert(next[4] == 3);
assert(next[5] == 4);
assert(next[6] == 5);
assert(next[7] == 6);
free(next);
next = kmp_calculate_next("abcdabd", 7);
assert(next[0] == 0);
assert(next[1] == 0);
assert(next[2] == 0);
assert(next[3] == 0);
assert(next[4] == 1);
assert(next[5] == 2);
assert(next[6] == 0);
free(next);
next = kmp_calculate_next("abcabaaabcda", 12);
assert(next[0] == 0);
assert(next[1] == 0);
assert(next[2] == 0);
assert(next[3] == 1);
assert(next[4] == 2);
assert(next[5] == 1);
assert(next[6] == 1);
assert(next[7] == 1);
assert(next[8] == 2);
assert(next[9] == 3);
assert(next[10] == 0);
assert(next[11] == 1);
free(next);
}
void test_kmp_string_match()
{
assert(kmp_string_match("abcabc", "abc") == 0);
assert(kmp_string_match("abcabc", "abcd") < 0);
assert(kmp_string_match("abcabcd", "abcd") == 3);
assert(kmp_string_match("bcabaaaa", "aaaa") == 4);
assert(kmp_string_match("bbcabcdababcdabcdabde", "abcdabd") == 13);
}
void test_kmp()
{
test_kmp_calculate_next();
test_kmp_string_match();
}