在字符串中查找子串函数

在字符串中查找子串是一种常见的操作，例如在文本编辑器中查找字符串，搜索引擎中搜索关键字等等。在本文中，我们将介绍如何编写一个简单的查找子串函数，并讨论优化该函数的方法。

首先，让我们明确一下函数的输入和输出。给定一个母串（字符串）和一个子串（字符串），函数将返回子串在母串中的位置。如果母串中不存在子串，则返回-1。函数原型如下：

int findSubstring(char* str, char* substr);

其中，str表示母串，substr表示子串。返回值为子串在母串中的位置，或者-1（表示没有找到子串）。

实现一个简单的查找子串函数非常容易。我们可以使用两个指针在母串中扫描子串，并在发现子串时返回其位置。具体实现如下：

int findSubstring(char* str, char* substr) {

    int i, j, k;

    for (i = 0; str[i] != '\0'; i++) {

        for (j = i, k = 0; substr[k] != '\0' && str[j] == substr[k]; j++, k++);

        if (substr[k] == '\0') {

            return i;

        }

    }

    return -1;

}

该函数内部使用了两个for循环。外层循环扫描母串，内层循环用两个指针依次扫描子串和母串。当扫描完成后，如果指针k指向了子串的结尾，则说明已经找到了子串，返回当前的母串位置i。如果外层循环结束后也没有找到子串，则说明不存在子串，返回-1。

该函数的时间复杂度为O(mn)，其中n是母串的长度，m是子串的长度。如果母串很长，而且子串很短，那么这种暴力算法的效率将非常低。因此，我们需要考虑如何优化这个函数。

一种简单的优化方法是使用KMP算法。KMP算法是一种快速的查找子串的算法，其时间复杂度为O(n+m)。KMP算法的核心是构造一个跳转表，用于在不匹配时快速跳转搜索位置。我们不在此处详细介绍KMP算法，感兴趣的读者可以查阅相关资料进行学习。

另一种优化方法是使用Boyer-Moore算法。Boyer-Moore算法是一种更加高效的查找子串的算法，其时间复杂度为O(n/m)~O(n)。Boyer-Moore算法的核心是利用不匹配的字符之前已知的信息来跳过大量的不必要的字符。Boyer-Moore算法是一种复杂的算法，实现起来相对困难。

总结一下，查找子串是一种常见的操作，其实现方法有多种。最简单的方法是使用暴力算法，但是随着数据规模的增大，效率会非常低下。因此，我们可以使用更高效的算法来提高查找子串的效率。在实际应用中，应该根据具体情况选择合适的算法来实现查找子串函数。