字符串朴素模式匹配算法
一、朴素模式匹配算法(简单模式匹配算法)思想:
将主串中与模式串长度相同的子串搞出来,挨个与模式串对比
当子串与模式串某个对应字符不匹配时,就立即放弃当前子串,转而检索下一个子串
若模式串长度为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 版权协议,转载请附上原文出处链接和本声明。