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
| #include <bits/stdc++.h>
//------------------------------------------------------------------------------------------------------
//暴力匹配：最简单的匹配算法
int index(SqString S, SqString p, int pos) //pos是从指定的位置进行匹配，P是输入的短的字符串
{
int i = pos - 1, j = 0;
while (i < S.length && j < P.length) //只要长度符合
{
if (S.SString[i] == P.SString[j])
{ //如果字符相同，就计数器，计位器都+1
i++;
j++;
}
else
{
/*如果不匹配，就计数器归零，这里详细讲一下计位器的
重置问题：假设第N次BF匹配失败，第N-1次BF匹配中计数器
增加了i(n-1)个位置，那么此时结束第N-1次BF匹配的时候，
计位器应该也已经跟着计数器“白白”跑了i(n-1)个位置，而
由于第N-1次BF匹配时，最后一个位置不匹配，那么此时的计
位器其实相对于计数器少走了一步，所以任意一次BF后，都有
j = j-i(减去陪计数器多走的步数) +1(少走的那一步);*/
i = i - j + 1; //计位器重置
j = 0; //计数器归零
}
}
//当然，最后还要判断一下计数器长度是否超标，也就是结果是否合法
if (j >= P.length) //如果匹配成功，那么计数器的值应该等于或者大于字符串的长度
return (i - P.length); //返回计位器在最后一BF匹配时的位置，也就是符合P的S中第一次出现的第一个字符的下标
else
return -1;
}
//显然这种算法的时间复杂度位O(m*n)，时间花费在每次匹配失败后的回退
//-------------------------------------------------------------------------------------------------
//KMP算法：改进版本的BF算法，每次匹配失败后不需要进行回退
//害，我这里还是有些懵逼，先记下这里的实现，后续学习之后我会进行更新
//失配函数next
void GetNext(SqString P, int next[])
{
int j, k;
j = 0;
k = -1;
next[0] = -1; //初始值
while (j < P.length - 1)
{
if (k == -1 || P.SString[j] == P.SString[k])
{
j++;
k++;
next[j] = k;
}
else
k = next[k];
}
}
//KMP算法
int Index_KMP(SqString S, Sqstring P, int pos)
{
int next[MaxSize], i = pos - 1, j = 0;
GetNext(P, next);
while (i < S.length && i < P.length)
{
if (j == -1 || S.String[i] == P.SString[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j >= P.length)
return (i - P.length);
else
return -1; //匹配失败
}
//-----------------------------------------------------------------------
//这里的next函数其实还是可以进行改进的
|