早就听闻串的KMP算法狠难搞,让我没想到的是,还没到KMP呢,在朴素模式匹配算法就让我猛喝了一壶,那么,今天就一起来看一看。
思路其实很简单,在上一节也提到过。首先我们先明确几个概念:
那么朴素模式匹配算法的思路就是:设模式串的长度为x,则把主串中每一个长度为x的子串和模式串对比。子串与模式串怎么对比呢?我们设置了两个整数变量,借助两个变量来一个字符一个字符比。
这里还是举个栗子🌰吧。
设要在子串为GOODGOOGLE中寻找模式串GOOGLE,我们可以知道模式串的长度为6,
为什么把这个条件单独列出来?因为我觉得它有点绕,我自己看了蛮久,也没有查到解释,最后自己想明白了。
试想一种情况,主串为GOODGOOGLE,模式串为GOOGLEE,按照上面的思路,我们循环到 i = 11;j = 7时因为i超出范围而结束循环,但此时j并没有超出模式串的长度,这样的情况也是匹配失败的。
在正常情况下,若能匹配成功,j最后指向的位置应是T.length + 1,因为在最后一次循环执行了j++操作,也就是说,只有j>T.length时,才表明模式串的所有字符都和某一子串完全匹配,而若 j <= L.length,表明因i超出范围而提前结束循环,匹配失败。
if(j>T.length)//就代表,j把T的长度走完了,代表匹配成功了,这里很绕!!
return i-T.length;
else//主串是abcd 模式串是cde,则循环到d时因为到达主串长度上限所以停止循环,但模式串没有到达长度上限,说明匹配失败。
return 0;
//暴力-简单模式匹配算法
int index(SString S,SString T){
int i = 1,j = 1;
while (i<=S.length && j<=T.length){
if(S.ch[i]==T.ch[j]){
i++;
j++;
}
else {
i = i - j + 2;//理解为 [i-(j-1)]+1 j-1 代表 j 移动了多少次,用i减去就表示回退这个小循环,然后+1,指向下一个字符
j = 1;
}
}
if(j>T.length)//就代表,j把T的长度走完了,代表匹配成功了,这里很绕!!
return i-T.length;
else//主串是abcd 模式串是cde,则循环到d时因为到达主串长度上限所以停止循环,但模式串没有到达长度上限,说明匹配失败。
return 0;
}