Algorithms/Knuth-Morris-Pratt.cpp at master · duanjigui/Algorithms · GitHub

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
#include <cstdio>
#include <cstring>

#define MAX_LENGTH 100000

using namespace std;

char T[MAX_LENGTH], P[MAX_LENGTH];
int pi[MAX_LENGTH];
int lt, lp;

void compute_prefix_function()
{
	int q = 0;
	pi[0] = 0;

	for (int i = 1; i < lp; i++)
	{
		while (q > 0 && P[i] != P[q])
		{
			q = pi[q - 1];
		}

		if (P[i] == P[q])
		{
			q++;
		}

		pi[i] = q;
	}
}

void KMP_matcher()
{
	compute_prefix_function();

	int q = 0;

	for (int i = 0; i < lt; i++)
	{
		while (q > 0 && T[i] != P[q])
		{
			q = pi[q - 1];
		}

		if (T[i] == P[q])
		{
			q++;
		}

		if (q == lp)
		{
			printf("matched with shift %d\n", i - lp + 1);
			q = pi[q - 1];
		}
	}
}

int main()
{
	gets(T);
	gets(P);
	lt = strlen(T);
	lp = strlen(P);

	KMP_matcher();

	return 0;
}