字符串模式匹配的Sunday算法

发表于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

C++代码实现字符串模式匹配的Sunday算法

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：

  • 只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符

    • 如果该字符没有在模式串中出现则直接跳过，一直移动到该字符之后出现的第一个与模式串首字符相同的字符，即移动位数 = 模式串长度 + 该字符之后出现的第一个与模式串首字符相同的字符到该字符的距离

    • 否则，其移动位数 = 模式串中最右端的该字符到末尾的距离+1

下面举个例子说明下Sunday算法。假定现在要在文本串”substring sasearching algorithm”中查找模式串”search”

  1. 刚开始时，把模式串与文本串左边对齐：

    substring sasearching algorithm
    search
    ^

  2. 结果发现在第2个字符处发现不匹配，不匹配时关注文本串中参加匹配的最末位字符的下一位字符，即标粗的字符 i，因为模式串search中并不存在i，所以模式串直接跳过一大片，向右移动位数 = 模式串长度 + 该字符之后出现的第一个与模式串首字符相同的字符到该字符的距离 = 6 + 4 = 10，从 i 之后的第一个与模式串首字符相同的字符（即字符s）开始下一步的匹配，如下图：

    substring sasearching algorithm

    search
^

  3. 结果第3个字符处不匹配，再看文本串中参加匹配的最末位字符的下一位字符，是’c’，它出现在模式串中的倒数第2位，于是把模式串向右移动2位（r 到模式串末尾的距离 + 1 = 1 + 1 =2），使两个’c’对齐，如下：

    substring sasearching algorithm
    　　　　 search
    　　　　　 ^

  4. 匹配成功

回顾整个过程，我们只移动了两次模式串就找到了匹配位置，缘于Sunday算法每一步的移动量都比较大，效率很高

下面给出C++实现Sunday算法的代码

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
#include<iostream>
#include<time.h>
#include<string.h>
using namespace std;

const int N = 255;
typedef char SString[N];//定义字符串类型SString

int getOffset(char letter, SString S) {
	int count = 0;
	for(int i = strlen(S) -1; i >= 0; i--) { // 从子串的最后一个开始搜索，如果
		if(S[i] == letter) {
			return strlen(S) - i;
		}
	}
	return -1;
}

int Sunday(SString S, SString T) {
	int pos = 0, i;
	while(pos <= strlen(T) - strlen(S)) {
		for(i = pos; i < pos + strlen(S); i++) {
			if(T[i] != S[i-pos]) break;
		}
		if(i == pos + strlen(S) ) {
			return pos;
		} 
		int offset = getOffset(T[pos + strlen(S)], S);
		if(offset > 0) pos += offset;
		else {
			while(T[pos] != S[0] || pos <= i) {
				pos++;
			}
		} 
	}
	return -1;
}

int main(){
	SString S,T;
	cout<<"input mainstring  T:";
	cin.getline(S, N+1);
	cout<<" intput substring S:";
	cin.getline(T, N+1);
	long start = clock();
	cout<<"the match pos ="<<Sunday(T, S)<<endl;
	long end = clock();
	cout << "running time:" << (double)(end - start) / CLOCKS_PER_SEC << "s"; 
	return 0;
}

作为对比，再给出KMP算法的实现代码，之后可以运行来看看两个的性能差距

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
#include<iostream>
#include<time.h>
#include<string.h>
using namespace std;

const int N = 255;
typedef char SString[N];//定义字符串类型SString

void getNext(SString T,int next[]){//计算next值
    int j=0,k=-1;//注意初值含义，j=0时k=-1，表示j之前不存在最长的前后缀串，即next[0]=-1
    next[0]=-1;//这种情况下表示一开始就匹配不上，使用KMP算法时候将同时把i，j后移
    while(j < strlen(T)){
        if(k==-1||T[j]==T[k]){ // j是后面那个, k是前面的
            //j++,k++,next[j]=k;
            next[++j]=++k;
            //上述代码的含义就是在next[j]=k的情况下,如果T[j]==T[k],则next[j+1]=k+1
            //或者k=-1条件下，让next[j+1]=0，表示j>0时候不存在相同的最长前后缀串即++k后k=0
        }
        else k=next[k];//如果T[j]≠T[k]，k跳转到next[k]继续循环匹配
    }
}

int KMP(SString A,SString B,int Pos){//KMP算法
    int i=Pos,j=0;
    int next[strlen(B)];//定义next数组
    getNext(B,next);//计算next数组的值
    for(int m=0;m<strlen(B);m++)
        cout << next[m] << " ";
    cout<< endl;
    while( i < strlen(A) && j < (int)strlen(B) ){
        if(j==-1||A[i]==B[j]) {
            i++;
            j++;
        } else {
            j=next[j];
        }
    }
    if(j==strlen(B))
        return i-j;
    else
        return -1;
}

int main(){
    SString S,T;
    cout<<"input mainstring  T:";
    cin.getline(T, N+1);
    cout<<" intput substring S:";
    cin.getline(S, N+1);
    long start = clock();
    cout<<"the match pos ="<<KMP(T,S,0)<<endl;
    long end = clock();
	cout << "running time:" << (double)(end - start) / CLOCKS_PER_SEC << "s"; 
    return 0;
}

Sunday算法的运行时间如图：

Migbb6.png

KMP算法的运行时间如图：

Mi2UMR.png

可以看到Sunday算法的效率更高