串的朴素模式匹配算法

串的朴素模式匹配算法

早就听闻串的KMP算法狠难搞，让我没想到的是，还没到KMP呢，在朴素模式匹配算法就让我猛喝了一壶，那么，今天就一起来看一看。

算法思路

思路其实很简单，在上一节也提到过。首先我们先明确几个概念：

• 主串：就是一个串，任何一个串都可以设为主串
• 子串：主串中连续字符组成的子序列，一定是主串中存在的才叫子串
• 模式串：想尝试在主串中找的串

那么朴素模式匹配算法的思路就是：设模式串的长度为x，则把主串中每一个长度为x的子串和模式串对比。子串与模式串怎么对比呢？我们设置了两个整数变量，借助两个变量来一个字符一个字符比。

这里还是举个栗子?吧。

设要在子串为GOODGOOGLE中寻找模式串GOOGLE，我们可以知道模式串的长度为6，

• 设 i 初始指向主串的第一个字符，j 初始指向模式串的第一个字符，一旦主串S[i]=模式串T[i]，i 与 j 就各自+1，比较下一个字符。
• 若出现S[i]!=T[i]，说明此子串与模式串匹配失败，于是下一个子串和模式串匹配，此时j的值变为1即可，问题是：如何把i的值变为下一个子串的第一个字符呢？
  • 答案即 i = [i-(j-1)]+1，这样看也许有些难懂，这里解释一下：j - 1即为j移动的次数，i-(j-1)即让 i 回退到j的小循环之前（因为i是和j一起移动的，所以 j 移动的次数等于 i 移动的次数），最后再[i-(j-1)]+1，+1是让i指向回退后的下一个位置，即下一个子串的起点

边界条件

为什么把这个条件单独列出来？因为我觉得它有点绕，我自己看了蛮久，也没有查到解释，最后自己想明白了。

试想一种情况，主串为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;
}