[TOC]

一、串的存储结构

1.顺序存储

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXLEN 255 //串的最大长度
typedef struct{
//串的定长顺序存储结构
char ch[MAXLEN+1]; //存储串的一位数组，下标0的分量闲置不用
int length; //串的当前长度
}

typedef struct{
//串的堆式顺序存储结构
char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL
int length;
}HString;

2.链式存储

1
2
3
4
5
6
7
8
9
#define CHUNKSIZE 80
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail; //串的头、尾指针
int length; //串的当前长度
}LString;

二、串的模式匹配算法

1.BF算法

  • 分别利用计数指针i和j，指示主串S和模式T中当前正待比较的字符位置，i初值为pos，j初值为0；

  • 如果两个串均未比较到串尾，即i和j均分别小于等于S和T的长度时，循环执行操作：

  • S.ch[i]和T.ch[i]比较，若相等，则i和j分别指示串中下一个位置，继续比较后续字符；

  • 若不等，指针后退重新匹配，从主串的下一个字符（i=i-j+2）起再重新和模式的第一个字符(j=0)比较；

  • 如果j>length，说明模式T的每个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，返回和模式T中第一个字符相等的字符在主串S中的符号（i-T.length），否则不成功，返回0。

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
//算法4.1　BF算法
int Index(SString S, SString T, int pos)
{
	//返回模式T在主串S中第pos个字符之后第s一次出现的位置。若不存在，则返回值为0
	//其中，T非空，1≤pos≤StrLength(S)
	int i = pos;
	int j = 1;
	while(i <= S[0]&&j <= T[0])
	{
		if(S[i]==T[j])
		{
			++i;
			++j;
		} //继续比较后继字符
		else
		{
			i=i-j+2;
			j=1;
		} //指针后退重新开始匹配
	}
	if (j > T[0])
		return i - T[0];
	else
		return 0;
	return 0;
}//Index

最好情况下的平均时间复杂度是O(n+m);

最坏情况下的平均时间复杂度是O(n*m).

2.KMP算法

特点：指针不需要回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//算法4.2　KMP算法
int Index_KMP(SString S, SString T, int pos, int next[])
{ 	// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
	//其中，T非空，1≤pos≤StrLength(S)
	int i = pos, j = 1;
	while (i <= S[0] && j <= T[0])
		if (j == 0 || S[i] == T[j]) // 继续比较后继字
		{
			++i;
			++j;
		}
		else
			j = next[j]; // 模式串向右移动
	if (j > T[0]) // 匹配成功
		return i - T[0];
	else
		return 0;
}//Index_KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//算法4.3　计算next函数值
void get_next(SString T, int next[])
{ //求模式串T的next函数值并存入数组next
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T[0])
		if (j == 0 || T[i] == T[j])
		{
			++i;
			++j;
			next[i] = j;
		}
		else
			j = next[j];
}//get_next