c++如何实现文本文件的全文搜索？KMP算法在流中的应用详解

在磁盘上找一个字符串到底出现在文件的哪个位置，听起来是个很简单的问题。很多人的第一反应是把文件整个读进内存，然后调用string::find完事。文件只有几KB的时候这确实没问题，可一旦面对日志文件、数据库dump这种动辄几个GB的大文件，这条路就走不通了：内存吃不消，读文件本身也要花掉大量时间。KMP算法的一个常被忽略的优点，就是它天然适配流式读取——主串指针永远只向前走，不需要回退。这个特性意味着我们完全可以一边从文件流里逐字符或逐块地读数据，一边做匹配，内存占用只和模式串长度有关，和文件大小彻底解耦。

一、KMP算法为什么适合流式处理

先回到算法本身。朴素的暴力匹配为什么慢？假设主串是"ABABABC"，模式串是"ABABC"。暴力做法是把主串和模式串逐字符比较，一旦失配，主串指针就退回到起始位置的下一个字符，模式串指针归零，重新来过。这样主串指针在不停地走回头路，最坏情况下时间复杂度是O(n×m)。

KMP的核心思想一句话概括：失配时主串指针不动，只调整模式串指针。为什么可以这样做？因为在匹配过程中，我们已经知道主串失配位置之前的那段字符，它们恰好等于模式串的前缀。模式串内部如果存在"既是前缀又是后缀"的重复结构（比如ABABC中，AB既是开头两个字符，也是失配前已匹配部分的结尾），就可以利用这个信息让模式串滑动到合适的位置继续比，主串一个字符都不用重读。

这个特性对流式处理至关重要。从ifstream读出来的字符是"过路客"，读过一次缓冲区就可能被覆盖，如果算法要求回退主串指针，就必须自己缓存历史数据，内存占用会随回退距离增长。而KMP每读一个字符最多只需要记住"当前匹配到了模式串的第几位"，这就是它能用一个固定大小缓冲区处理无限大文件的根本原因。

二、手写KMP：next数组构建与匹配逻辑

next数组（有的资料叫failure function或前缀函数）记录的是：模式串每个位置之前的子串中，最长的"相等真前缀与真后缀"的长度。构建next数组只依赖模式串自身，和主串无关，所以可以在读取文件之前一次性算好。

#include <vector>
#include <string>

// 构建next数组，next[i]表示p[0..i]中最长相等前后缀的长度
std::vector<int> buildNext(const std::string& p) {
    int m = p.size();
    std::vector<int> next(m, 0);
    int k = 0;  // 当前最长相等前后缀长度
    for (int i = 1; i < m; ++i) {
        // 失配则沿着next链回退
        while (k > 0 && p[i] != p[k]) {
            k = next[k - 1];
        }
        if (p[i] == p[k]) {
            ++k;
        }
        next[i] = k;
    }
    return next;
}

匹配函数的写法和构建过程非常相似，几乎是同一套逻辑套在两个串上。注意看主串指针i在循环里只增不减：

// 返回模式串在主串中所有出现位置的起始下标
std::vector<long long> kmpSearch(const std::string& s,
                                  const std::string& p,
                                  const std::vector<int>& next) {
    std::vector<long long> result;
    int n = s.size(), m = p.size();
    int j = 0;  // 模式串匹配指针
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];  // 主串i不回退，只回退j
        }
        if (s[i] == p[j]) {
            ++j;
        }
        if (j == m) {
            result.push_back((long long)i - m + 1);
            j = next[j - 1];  // 继续找下一处，允许重叠匹配
        }
    }
    return result;
}

两段代码里都有while (k > 0 && ...)这样的回退循环，这不是巧合，而是KMP的自相似结构：求解next数组的过程，本质上就是模式串自己做KMP匹配。理解了这一点，这两段代码就不用分开死记了。整个算法的时间复杂度是O(n+m)，即使文件有几个GB，也只需要一遍线性扫描。

三、基于ifstream的流式文件搜索实现

有了上面的匹配函数，把主串从内存字符串换成文件流就是水到渠成的事。最直接的做法是逐字符读取，每读一个字符推进一次匹配状态：

#include <fstream>
#include <iostream>

// 在文件中流式搜索，返回所有匹配位置（字节偏移）
void searchFile(const char* filepath, const std::string& pattern) {
    std::vector<int> next = buildNext(pattern);
    std::ifstream fin(filepath, std::ios::binary);
    if (!fin) {
        std::cerr << "无法打开文件" << std::endl;
        return;
    }
    int m = pattern.size();
    int j = 0;              // 当前匹配到的模式串位置
    long long pos = 0;      // 当前文件字节偏移
    char ch;
    while (fin.get(ch)) {
        while (j > 0 && ch != pattern[j]) {
            j = next[j - 1];
        }
        if (ch == pattern[j]) ++j;
        if (j == m) {
            std::cout << "在偏移 " << pos - m + 1
                      << " 处找到匹配" << std::endl;
            j = next[j - 1];  // 继续搜索后续出现
        }
        ++pos;
    }
}

注意打开文件时要加上std::ios::binary标志。如果不加，Windows下文本模式会把\r\n转换成\n，导致字节偏移量和实际文件内容对不上，搜索包含回车符的模式时还会直接失配。这是实际工程里非常容易踩的一个坑。

逐字符get虽然正确，但每个字符一次流提取调用，函数开销不小。更快的做法是按块读取，一次读几MB到缓冲区，在块内循环匹配，块与块的衔接处需要把模式串末尾的m-1个字符带到下一块开头，防止匹配恰好跨块边界时漏掉：

void searchFileChunked(const char* filepath, const std::string& pattern) {
    std::vector<int> next = buildNext(pattern);
    std::ifstream fin(filepath, std::ios::binary);
    const size_t BUF = 4 * 1024 * 1024;  // 4MB缓冲区
    const size_t overlap = pattern.size() - 1;
    std::string buf(BUF + overlap, '\0');
    long long filePos = 0;
    while (fin.read(&buf[overlap], BUF) || fin.gcount() > 0) {
        size_t got = fin.gcount();
        int j = 0;
        for (size_t i = 0; i < overlap + got; ++i) {
            while (j > 0 && buf[i] != pattern[j]) j = next[j - 1];
            if (buf[i] == pattern[j]) ++j;
            if (j == (int)pattern.size()) {
                std::cout << "偏移 " << filePos + (long long)i
                          << " 处匹配" << std::endl;
                j = next[j - 1];
            }
        }
        // 把本块结尾的overlap个字符搬到下一块开头
        std::copy(buf.begin() + got, buf.begin() + got + overlap,
                  buf.begin());
        filePos += got;
        if (got < BUF) break;  // 文件读完
    }
}

这里的overlap搬运逻辑值得仔细看：上一块的最后m-1个字符被复制到缓冲区开头，新数据从&buf[overlap]处开始写入，两段拼在一起构成连续文本，匹配状态在这段拼接区域内自然延续，不需要任何特殊处理。代价是每块多比较了m-1个字符，量级上完全可以忽略。

四、方案对比与工程建议

最后把常见做法放在一张表里对比一下：

几点工程上的补充。第一，如果要做大小写不敏感搜索，不要在每个字符比较时反复调用tolower，更好的办法是在构建next数组和匹配时统一做一次预处理，或者干脆把模式和文件内容都转成小写再比。第二，如果同一个文件要反复用不同关键词搜索，可以考虑用mmap把文件映射进内存，省去重复的系统调用，匹配算法本身照旧用KMP。第三，多模式同时搜索的需求下，KMP就不合适了，应该换用Aho-Corasick自动机，它相当于多个模式串共享一棵失配树，一次扫描能同时匹配所有模式。

总结一下关键点：KMP失配时主串指针不回退的特性，使它成为流式文本搜索的理想选择；分块读取加overlap拼接，可以在保证正确性的前提下大幅提升吞吐；binary模式打开文件是处理偏移量的前提。掌握这套思路之后，无论是实现一个简易的grep，还是在日志系统中做实时关键字过滤，都有了扎实的基础。

C++文件搜索KMP算法流式读取修改时间：2026-09-07 14:52:54