串的模式匹配问题

Share 
INDEX(S, T, pos)
  • 初始条件

串S和T存在，T是非空串， 1 <= pos <= strLength(S)

  • 操作结果

若主串S中存在和串T值相同的子串，返回它在主串S中第pos个字符之后首次出现的位置；否则函数值为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int INDEX(string S, string T, int pos) {
	//T 为非空串。
	//若主串S中存在和串T值相同的子串，返回它在主串S中第pos个字符之后首次出现的位置；否则函数值为0
	if (pos > 0) {
		n = strLength(S);
		m = strLength(T);
		i = pos;
		while (i <= n-m+1) {
			subString(sub, S, i, m);
			if (strCompare(sub, T) != 0) {
				++i;
			} else 
				return i;
		}
	}
	return 0;
}

下面讨论定长顺序结构表示串时的几种算法

  • 简单算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int easyIndex(string S, string T, int pos) {
	//返回子串T在主串S中第pos个字符之后的位置，若不存在，则返回0
	//其中，T非空， 1 <= pos <= strLength(S)
	i = pos;
	j = 1;
	while (i <= S[0] && j <= T[0]) {
		//S[0] 与 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;
}
  • 首尾匹配算法

先比较模式串中的第一个字符，在比较模式串中的第n个字符，最后比较模式串中从第2个到第n-1个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int headPostIndex(string S, string T, int pos) {
	sLength = S[0];
	tLength = T[0];
	i = pos;
	aptStartChar = T[1];
	aptEndChar = T[tLength];
	while (i <= sLength - tLength + 1) {
		if (S[i] != patStartChar) {
			//重新查找匹配初始点
			++i;
		} else if (S[i+tLength-1] != patEndChar) {
			//模式串中的“尾字符”不匹配
			++i;
		} else {
			//检查中间字符的匹配情况
		}
	}
	return 0;
}
  • KMP算法

详情请戳我的另一篇文章http://www.saberismywife.com/2016/10/13/谈一谈KMP算法/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int KMPIndex(string S, string T, int pos) {
	i = pos;
	j = 1;
	while (i <= S[0] && j <= T[o]) {
		if (j == 0 || S[i] == T[j]) {
			//继续比较后继字符
			++i;
			++j;
		} else 
			//模式串向后移动
			j = next[j];
	}
	if (j > T[0]) {
		//匹配成功
		return i-T[0];
	} else 
		return 0;
}