如何不使用find()函数判断子串存在？能否优化匹配算法复杂度？

一、不使用find()判断子串存在的基础实现 #

你贴的这段代码是典型的暴力匹配法，核心逻辑很直白：

1. 遍历主串s2的每个可能起始位置（范围是0到N-M，避免越界）
2. 对每个起始位置，逐个对比子串s1和主串对应位置的字符
3. 如果所有字符都匹配，返回起始索引；遍历完所有位置都没匹配则返回-1

这种方法的时间复杂度在最坏情况下是O(M*(N-M))（比如主串全是"aaaaa..."，子串是"aaaab"），数据量大时效率很低。

二、如何降低时间复杂度？ #

当然可以，下面几种经典算法能把时间复杂度降到线性级别（O(M+N)），甚至在特定场景下比标准库的find()更高效：

1. KMP算法 #

KMP的核心是避免主串指针回溯。通过预处理子串生成最长前缀后缀数组（LPS），当字符不匹配时，利用已匹配的部分信息，直接把子串指针跳到合适位置，不用从头再对比。

以下是C++实现示例：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 生成LPS数组：记录子串每个位置的最长相等前缀后缀长度
void computeLPS(string pat, vector<int>& lps) {
    int len = 0; // 最长前缀后缀的长度
    lps[0] = 0;
    int i = 1;
    int M = pat.size();
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len-1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmpSearch(string txt, string pat) {
    int N = txt.size();
    int M = pat.size();
    vector<int> lps(M);
    computeLPS(pat, lps);
    
    int i = 0; // 主串指针
    int j = 0; // 子串指针
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }
        if (j == M) {
            return i - j; // 返回起始索引
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j-1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

int main() {
    string txt = "geeksforgeeks";
    string pat = "for";
    int res = kmpSearch(txt, pat);
    if (res == -1)
        cout << "Not present";
    else
        cout << "Present at index " << res;
    return 0;
}

KMP的预处理时间是O(M)，匹配时间是O(N)，整体复杂度O(M+N)，适合需要重复查找同一子串的场景。

2. Boyer-Moore算法 #

Boyer-Moore从子串的末尾开始匹配，利用两个规则跳过大量不必要的比较：

• 坏字符规则：当主串当前字符和子串不匹配时，直接把子串移动到该字符在子串中最后出现的位置之后
• 好后缀规则：如果已经匹配了一部分子串，利用这部分后缀的信息，移动子串到能继续匹配的位置

这种算法在实际文本搜索中表现极佳，平均时间复杂度接近O(N)，最坏情况虽为O(M*N)但出现概率极低。

3. Rabin-Karp算法（哈希匹配） #

Rabin-Karp通过哈希值快速筛选：

1. 先计算子串的哈希值
2. 滚动计算主串中每个长度为M的子串的哈希值（利用前一个子串的哈希值，避免重复计算）
3. 只有当哈希值相等时，才进行逐字符验证（避免哈希冲突）

这种算法的时间复杂度也是O(M+N)，适合多模式匹配（比如同时查找多个子串）的场景。

关于标准库find()的效率 #

C++标准库的string::find()实现通常是优化后的暴力法或类似Boyer-Moore的算法，大多数场景下足够高效，但如果处理超长文本或需要高频次查找，上面提到的KMP、Boyer-Moore会表现得更好。

内容的提问来源于stack exchange，提问作者Chaitanya Rustagi