一些基本概念
- 定义的
一个或多个字符组成的有限序列，又叫字符串
- 子串与主串
- 连续字符组成的子序列称为该串的子串
- 包含子串的串称为主串
串的比较
方法
-
通过在Unicode中的顺序（Unicode的前256个字符与ASCII相同）比较
-
例子
- 当给定两个串$s=“a_1a_2…a_n”,t=“b_1b_2…b_n”$时，当且仅当$a_i=b_i,i=1,2…,n$时，我们认为$s=t$
串的ADT
串的存储结构
顺序存储结构
链式存储结构
朴素的模式匹配算法
算法说明
对字串的每一个字符作为子串的开头，与目标进行匹配
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int Index(String S, String T, int pos)
{
int i = pos; //主串当前位置下标
int j = 1; // 子串中当前位置下标
while(i <= StringLength(S) && j <= StringLength(T))
{
if(S[i] == T[j])
{
i++;
j++;
}
else
{
i = i-j+2;
j=1;
}
}
if (j > StringLength(T))
return i-T[0];
else
return 0;
}
|
KMP模式匹配算法
原理
-
i、j分别为S和T的下标
-
定义$next[j]$
$$
next[j] =\begin{cases} 0 & j =1 \\
Max \lbrace k | 1\lt k \le (j-1) ，且 ‘p_1p_2…p_{k-1}’ = ‘p_{j-k+1}…p_{j-1}’ \rbrace & 当此集合不空时
\\ 1 & 其他情况
\end{cases}
$$
从$1$到$j-1$相同的字符串
- $next$值推导的例子
| $j$ |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| $T$ |
a |
a |
a |
a |
a |
a |
a |
a |
b |
| $next[j]$ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
- 代码实现
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
|
// Next数组的实现
void get_next(String T,int *next)
{
int i,j;
i = 1;
j = 0;
next[1] = 0;
while(i<StringLength(T))
{
if (j==0 || T[i] == T[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
// 返回子串T在S中第pos个字符后的位置
int Index_KMP(String S, String T, int pos)
{
int i = pos;
int j = 1;
int next[255];
get_next(T,next); //对串T作分析，得到next数组
while(i <= StringLength(S) && j <= StringLength(T))
{
if (j == 0 || S[i] = T[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j>StringLength(T))
return i-StringLength(T);
else
return 0;
}
|
KMP模式匹配算法的改进
- 设置$nextval[j]$ 数组
| $j$ |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| $T$ |
a |
b |
a |
b |
a |
a |
a |
b |
a |
| $next[j]$ |
0 |
1 |
1 |
2 |
3 |
4 |
2 |
2 |
3 |
| $nextval[j]$ |
0 |
1 |
0 |
1 |
1 |
4 |
2 |
1 |
0 |
1
2
3
4
5
6
7
8
9
|
void get_nextval(String T, int *nextval)
{
if (j==0 || T[i] == T[j])
{
i++;
j++;
if ()
}
}
|