C程序的朴素模式搜索算法

1. 什么是朴素模式搜索算法

朴素模式搜索算法（也称为暴力算法）是一种简单的字符串匹配算法。其思想是从主串的第一个字符开始，与模式串的第一个字符依次比较，如果相等则继续比较下一个字符，如果不相等则从主串的下一个字符重新开始匹配。该算法的时间复杂度是O(n*m)，其中n和m分别为主串和模式串的长度。

2. 朴素模式搜索算法的实现

2.1 算法流程

朴素模式搜索算法的实现步骤如下：

在主串S中，从第一个字符开始依次比较，如果该字符与模式串P中的第一个字符相等，则进入第2步；否则继续比较主串中的下一个字符。

依次比较主串S和模式串P中的每个字符，如果全部相等，则匹配成功，返回主串中的匹配位置；否则从主串S中下一个字符开始重新比较。

如果主串S的长度小于模式串P的长度，则匹配失败，返回-1。

2.2 代码实现

int naive_search(const char* s, const char* p)
{
    int slen = strlen(s);
    int plen = strlen(p);
    for (int i = 0; i <= slen - plen; i++)
    {
        int j;
        for (j = 0; j < plen; j++)
        {
            if (s[i+j] != p[j])
                break;
        }
        if (j == plen)
            return i;
    }
    return -1;
}

在这段代码中，首先获取主串S和模式串P的长度。然后在主串S中从第一个字符开始依次比较，如果和模式串P中的第一个字符相等，则进入内层循环进行依次比较，如果比较的字符均相等，则匹配成功，返回主串中的匹配位置；否则从主串S中下一个字符开始重新比较。如果主串S的长度小于模式串P的长度，则匹配失败，返回-1。

3. 朴素模式搜索算法的优缺点

3.1 优点

朴素模式搜索算法实现简单、效率高，对于较短的主串和模式串有较好的匹配效果。

3.2 缺点

朴素模式搜索算法的时间复杂度为O(n*m)，其中n和m分别为主串和模式串的长度。因此，对于较长的主串和模式串，该算法效率下降明显。

4. 总结

朴素模式搜索算法是一种简单但效率较高的字符串匹配算法。它的实现思路简单，实现代码也比较容易理解。但是由于算法的时间复杂度较高，对于较长的主串和模式串匹配效率不高。因此，在实际应用中，需要根据具体的情况选择合适的字符串匹配算法。