递归函数在C++中进行子串搜索

1. 什么是递归函数

递归函数是指在函数体内调用自己的函数。这种调用方式被称为递归调用。

递归函数的特点是它在执行过程中会调用自己，并且每次调用时传入的参数不同，所以递归函数可以用来解决一些需要不断重复执行某一过程的问题，常用于搜索、遍历等场景。

int factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n-1);
}

上面的代码是一个计算阶乘的递归函数，在函数体内它调用了自己，并且每次传入的参数都比上一次小一，直到传入1停止调用自身，返回1。

2. 子串搜索

2.1 概括

子串搜索是指再一个字符串中查找特定的子串（一个字符串的一部分）。子串搜索是计算机科学和信息科学中广泛使用的一个问题，常被用于搜索引擎、文本编辑器等领域。

2.2 顺序搜索算法

最朴素的子串搜索算法是线性算法，该算法的时间复杂度是O(n^2)，即需要遍历整个字符串，并在每个位置开始检查子串是否匹配。

下面是一个使用顺序搜索算法实现的子串搜索函数：

int substring_search(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++)
            if (text[i + j] != pattern[j])
                break;
        if (j == m) return i; //找到了
    }
    return -1; //未找到
}

上面的代码通过两个嵌套循环来查找子串，外层循环遍历字符串的每个字符，内层循环在每个位置上从子串的第一个字符开始检查是否匹配。

2.3 KMP算法

KMP算法是一种更为高效的子串搜索算法，其时间复杂度是O(n+m)，其中n为字符串长度，m为子串长度。KMP算法的核心思想是在匹配过程中不回退主串中的指针。

下面是KMP算法的实现代码：

void get_next(const string& pattern, vector& next) {
    int m = pattern.length();
    int j = 0, k = -1;
    next[0] = -1;
    while (j < m - 1) {
        if (k == -1 || pattern[j] == pattern[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}
int kmp(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector next(m);
    get_next(pattern, next);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == m) {
        return i - m;
    } else {
        return -1;
    }
}

上面的代码中，get_next函数在匹配前先生成一个next数组，该数组存储了子串在某个位置出现不匹配时应该跳到哪里继续匹配。这个next数组的生成方式是通过匹配前缀和后缀来得到，具体可以看代码中的注释。

3. 代码示例

下面是一个使用递归函数实现的子串搜索函数：

bool match(const string& text, const string& pattern, int i, int j) {
    if (i == text.length()) return j == pattern.length();
    if (j == pattern.length()) return false;
    if (text[i] == pattern[j] || pattern[j] == '?') {
        return match(text, pattern, i+1, j+1);
    } else if (pattern[j] == '*') {
        return match(text, pattern, i+1, j) || match(text, pattern, i, j+1);
    } else {
        return false;
    }
}
bool substring_search(const string& text, const string& pattern) {
    return match(text, pattern, 0, 0);
}

上面的代码中，match函数是用来判断当前位置是否匹配的递归函数，它根据当前字符是否相同或是通配符（?和*）来判断是否匹配，并分别递归匹配下一个字符或是起始下一个子串。

4. 总结

本文主要介绍了递归函数的基本概念以及如何使用递归函数实现子串搜索。除了常见的顺序搜索算法外，KMP算法是一种更为高效的子串搜索算法，该算法的核心思想是在匹配过程中不回退主串中的指针。

通过使用递归函数实现子串搜索，我们可以在极短的代码中实现高效的字符串匹配算法，同时也能够较为清晰地表达算法思路。