Sunday子串查找算法

问题描述:

给定字符串A、B,在A中查找子串B是否存在,若找到则返回下标,若没有找到则返回-1。

例如:给定A为”helloworld”,B为”rld”,则返回7,B为”rlb”,则返回-1。

典型的子串查找算法有4种(见下表)。本文只描述暴力算法和Sunday算法。

算法 平均复杂度 最坏复杂度 是否回退
暴力 O(N) O(N*M) Yes
BM O(N/M) O(N*M) Yes
KMP O(N) O(N) No
Sunday O(N/M) O(N*M) Yes

表:四种子串查找算法的对比

暴力算法:

暴力算法直观地从A串的第0个字符尝试匹配B,若不匹配则从下一个字符尝试匹配B……直到匹配到B为止。平均复杂度为O(N),最坏情况下,比如A为”aaaaaaaaaaaaab”,B为”aaaaab”时,每次尝试匹配都需要达到B的末尾才结束,复杂度达到O(N*M)。

 

Sunday算法:

 

Sunday算法与BM算法类似,是一个常规情况下很快,极端情况下很慢的算法。而它的代码比BM算法简单一些。思路是:先从A串的0下标尝试匹配B,若匹配在某处失败了,需要到“下一个位置”重新尝试匹配,即尝试匹配的位置需要后移。对于暴力算法,每次只后移1个字符,即“下一个位置”等价于“下一个字符”。而Sunday算法的后移方式聪明一些:先找到“A中失配字符串的下一个字符c”,再寻找c在B中从右向左的第一个位置,若找到则把两个c对齐并尝试匹配,若未找到就从c的下一个字符开始匹配。

这种描述很抽象,用图解大概能明白:

 

图:图解暴力算法和Sunday算法

 

预备Next数组:

需要注意的问题是:如何把算法思想转换为程序,能在匹配失败时高效地右移B到合适的位置。

我们的做法是,在查找之前,做一个预处理,准备一个缓存数组int next[256],256是char型变量的个数,因此next数组的每一个元素都对应一个字符的ASCII码。在查找进行时,每次匹配失败时,B右移next[c]个字符。

next数组需要根据B串确定:对于字符c,M-next[c]是c在B中的最后一个下标。若c在B中不出现,则next[c]=M+1

这样,在算法执行时,当匹配失败,我们获取到“A中失配字符串的下一个字符c”,然后把B右移next[c]个字符重新尝试匹配即可。由于事先初始化了next数组,若c在B串中出现且最后出现的下标为i,则B右移M-i个字符,刚好能让两个c对齐;若c在B串中不出现,则右移M+1个字符,正好能让B移动到c的下一个位置开始匹配。

由于多数情况下Sunday算法能让B移动接近M个字符,因此平均复杂度为O(N/M),但是极端情况下:例如A为”aaaaaaaaaaaaab”,B为”aaaaab”,复杂度为O(N*M)

 

代码:

这里给出一个完整的C语言暴力算法和Sunday算法测试程序:

#include "stdio.h"
#include "string.h"

/* 暴力算法,在str中寻找pat的位置 */
int search(char *pat,char *str){
	int i,j,len;
	for(i=0;str[i]!='\0';i++){
		for(j=0;pat[j]!='\0'&&pat[j]==str[i+j];j++);
		if(pat[j]=='\0') return i;
	}
	return -1;
}

/* Sunday算法,在str中寻找pat的位置 */
int sunday_search(char *pat,char *str){
	int i,j,len;
	int next[256] = {0};
	len = strlen(pat);
	for(j=0;j<256;j++) next[j] = len+1;
	for(j=0;j<len;j++) next[(unsigned char)pat[j]] = len-j;
	for(i=0;;i+=next[(unsigned char)str[i+len]]){
		for(j=0;j<len&&str[i+j]==pat[j];j++);
		if(j>=len) return i;
		else if(str[i+j]=='\0') return -1;
	}
}

main(){
	char A[] = "helloworld";
	char B[] = "rld";
	int r1, r2;
	r1 = search(B,A);
	r2 = sunday_search(B,A);
	printf("%d,%d\n", r1, r2);
}

运行结果是7,7,即在”helloworld”中查找”rld”,两种算法返回的位置都是7。你可以尝试让A是一个很长的英文段落,B是其中的一句话,试试两种算法的耗时。