AlgorithmAnalysisAndDesign/kmp.cpp at master · yunshouhu/AlgorithmAnalysisAndDesign · 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include <iostream>
#include <string>
#include <time.h>
#include <vector>
#include <windows.h>
using namespace std;


/*
* 从s中第sIndex位置开始匹配p
* 若匹配成功，返回s中模式串p的起始index
* 若匹配失败，返回-1
*/
int index(const std::string &s, const std::string &p, const int sIndex = 0)
{
	int i = sIndex, j = 0;

	if (s.length() < 1 || p.length() < 1 || sIndex < 0)
	{
		return -1;
	}

	while (i != s.length() && j != p.length())
	{
		if (s[i] == p[j])
		{
			++i;
			++j;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	return j == p.length() ? i - j : -1;
}

void getNext(const std::string &p, std::vector<int> &next);

int kmp(const std::string& s, const std::string& p, const int sIndex = 0)
{
	std::vector<int>next(p.size());
	getNext(p, next);//获取next数组，保存到vector中

	int i = sIndex, j = 0;
	while (i != s.length() && j != p.length())
	{
		if (j == -1 || s[i] == p[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}

	return j == p.length() ? i - j : -1;
}

void getNext(const std::string &p, std::vector<int> &next)
{
	next.resize(p.size());
	next[0] = -1;

	int i = 0, j = -1;

	while (i != p.size() - 1)
	{
		//这里注意，i==0的时候实际上求的是next[1]的值，以此类推
		if (j == -1 || p[i] == p[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
		{
			j = next[j];
		}
	}
}

void getNextUpdate(const std::string& p, std::vector<int>& next)
{
	next.resize(p.size());
	next[0] = -1;

	int i = 0, j = -1;

	while (i != p.size() - 1)
	{
		//这里注意，i==0的时候实际上求的是nextVector[1]的值，以此类推
		if (j == -1 || p[i] == p[j])
		{
			++i;
			++j;
			//update
			//next[i] = j;
			//注意这里是++i和++j之后的p[i]、p[j]
			next[i] = p[i] != p[j] ? j : next[j];
		}
		else
		{
			j = next[j];
		}
	}
}
void mysleep()
{
#if defined(_WIN32)

	Sleep(1000);//1s
#else
#include <syswait.h>
	sleep(1);//1s
#endif
}
//http://www.cnblogs.com/goagent/archive/2013/05/16/3068442.html
int main()
{
	time_t start, end;
	time(&start);
	cout << index("xxabcxxabcxxxabcxdabctdeefghijkkklmn123456ooabcdefdd", "abcd") << endl;
	mysleep();
	time(&end);


	printf("index 花费时间 %f秒\n", difftime(end, start));

	time(&start);
	cout << kmp("xxabcxxabcxxxabcxdabctdeefghijkkklmn123456ooabcdefdd", "abcd") << endl;

	mysleep();
	time(&end);
	printf("kmp 花费时间 %f秒\n", difftime(end, start));

	return 0;
}