4.1字符串匹配的朴素实现

​

​ 很多情况，我们都会遇到字符串的匹配问题，比如说，你在QQ上或者手机通讯录上输入一组数字，当我们逐个输入后，会发现，所有的关于你当前输入的号码（数字）的相关好友、电话都显示出来了。我们想要实现这种功能，可以将其转化为字符串的模式匹配问题。其中，最容易想到的方法就是朴素搜索算法。什么是朴素搜索算法呢？它又称暴力搜索。这么来说吧，就是我拿着模式串和主串（带查找的字符串）一个一个字符进行比较。这么做我是一定可以得到正确结果的。

​ 它的思路是这样的：先从第一个位置（主串），逐个比对，如果发现有一个不同，停止比对，从下一个位置继续逐个比对。一直循环下去，直到找到第一个匹配成功的，或者被查找的字符串（主串）到达末尾。示意图如下：

​ 然后就是我们的实现代码，这里给出C语言的：

int BF(char str[], char s[])
{
    int len1 = strlen(str);
    int len2 = strlen(s);
    int i = 0;
    int j = 0;

    while (i < len1 && j < len2) {
        if (str[i] == s[j]) {
            i++;
            j++;
        }
        else {
            i = i - j + 1;
            j = 0;
        }
    }

    return (j >= len2) ?  i-j : -1;
}

​ 怎么样，是不是很简单？恭喜你又掌握了一个技能！不过，这种算法的时间复杂度太高了。下次我们会讲另一种改进的模式匹配算法：KMP算法。