字符串朴素模式匹配算法(简单模式匹配算法)

  • Post author:
  • Post category:其他




字符串朴素模式匹配算法



一、朴素模式匹配算法(简单模式匹配算法)思想:

将主串中与模式串长度相同的子串搞出来,挨个与模式串对比

当子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串

若模式串长度为m,主串长度为n,则直到匹配成功/匹配失败最多需要(n-m+1)*m次比较

最坏时间复杂度: O(nm)

最坏情况:每个子串的前m-1个字符都和模式串匹配,只有第m个字符不匹配

比较好的情况:每个子串的第1个字符就与模式串不匹配



二、代码实现

方案一:

//方案① 
int Index(String S,String T){
	int i,j;
	int k=1;
	while(i<=S.length&&j<=T.length){
		if(S.ch[i]==T.ch[j]){
			i++;
			j++
		}
		else{
			i=k;
			j=1;
			k++;
		}
	}
	if(j>T.length){
		return k;
	}
	else return 0;
}

方案二:

//方案② 
int Index(String S,String T){
	int i,j;
	while(i<=S.length&&j<=T.length){
		if(S.ch[i]==T.ch[j]){
			i++;
			j++
		}
		else{
			i=i-j+2;
			j=1;
		}
	}
	if(j>T.length){
		return i-T.length;
	}
	else return 0;
}



版权声明:本文为weixin_44279771原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。