如何在千万位数字文本中高效查找模式串并获取起始位置

一、Java 流式KMP匹配方案（适配多次查询） #

针对大文件无法全量加载的问题，采用流式读取+KMP算法，既避免内存溢出，又保证匹配效率，适合多次重复查询。

核心思路 #

1. 用BufferedReader按1MB块读取文件，避免一次性加载全量数据
2. 维护KMP算法的当前匹配状态，以及块末尾的模式串长度-1个字符（处理跨块的模式匹配）
3. 累计已读取的字符数，计算每个匹配的起始位置
4. 将结果写入输出文件

实现代码 #

import java.io.*;

public class KMPBigFileMatcher {
    private static int[] buildKMPTable(String pattern) {
        int patternLength = pattern.length();
        int[] lps = new int[patternLength];
        int len = 0;
        int i = 1;
        while (i < patternLength) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                len = len != 0 ? lps[len - 1] : 0;
                if (len == 0) {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void matchPattern(String filePath, String pattern, String outputPath) throws IOException {
        int patternLength = pattern.length();
        if (patternLength < 32 || patternLength > 4096) {
            throw new IllegalArgumentException("模式串长度需在32-4096之间");
        }
        int[] lps = buildKMPTable(pattern);
        long totalCharsRead = 0;
        int currentState = 0;
        StringBuilder leftover = new StringBuilder();

        try (BufferedReader reader = new BufferedReader(new FileReader(filePath), 1024 * 1024);
             BufferedWriter writer = new BufferedWriter(new FileWriter(outputPath))) {

            char[] buffer = new char[1024 * 1024];
            int charsRead;
            while ((charsRead = reader.read(buffer)) != -1) {
                // 拼接上一次的剩余字符
                char[] combined = new char[leftover.length() + charsRead];
                leftover.getChars(0, leftover.length(), combined, 0);
                System.arraycopy(buffer, 0, combined, leftover.length(), charsRead);
                leftover.setLength(0);

                int combinedLength = combined.length;
                for (int i = 0; i < combinedLength; i++) {
                    while (currentState > 0 && combined[i] != pattern.charAt(currentState)) {
                        currentState = lps[currentState - 1];
                    }
                    if (combined[i] == pattern.charAt(currentState)) {
                        currentState++;
                    }
                    if (currentState == patternLength) {
                        long startPos = totalCharsRead - (combinedLength - i - 1);
                        writer.write(String.valueOf(startPos));
                        writer.newLine();
                        currentState = lps[currentState - 1];
                    }
                }

                // 保存末尾的patternLength-1个字符用于下一块匹配
                if (combinedLength >= patternLength - 1) {
                    leftover.append(combined, combinedLength - (patternLength - 1), patternLength - 1);
                } else {
                    leftover.append(combined);
                }
                totalCharsRead += charsRead;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String inputFile = "big_numbers.txt";
        String pattern = "your_32_to_4096_digit_pattern";
        String outputFile = "match_positions.txt";
        matchPattern(inputFile, pattern, outputFile);
    }
}

二、Node.js 流式BM匹配方案（适合前端/Node环境） #

用Node.js的流式API处理大文件，结合BM算法（实际场景中平均效率优于KMP），避免全量加载内存。

核心思路 #

1. 创建可读流逐块读取文件
2. 维护BM算法的坏字符表和好后缀表，以及块末尾的模式串长度-1个字符
3. 累计已读取字符数（ASCII数字字节数等于字符数）
4. 匹配到的位置写入输出文件

实现代码 #

const fs = require('fs');

// 构建BM坏字符表
function buildBadCharTable(pattern) {
    const table = new Array(128).fill(-1);
    for (let i = 0; i < pattern.length; i++) {
        table[pattern.charCodeAt(i)] = i;
    }
    return table;
}

// 构建BM好后缀表
function buildGoodSuffixTable(pattern) {
    const patternLen = pattern.length;
    const suffix = new Array(patternLen).fill(0);
    const prefix = new Array(patternLen).fill(false);
    suffix[patternLen - 1] = patternLen;

    let i = patternLen - 2;
    while (i >= 0) {
        let j = i;
        while (j >= 0 && pattern.charAt(j) === pattern.charAt(patternLen - 1 - (i - j))) j--;
        suffix[i] = i - j;
        i--;
    }

    i = 0;
    while (i < patternLen - 1) {
        if (suffix[i] === i + 1) {
            for (let j = patternLen - 1 - i; j < patternLen; j++) {
                if (!prefix[j]) prefix[j] = true;
            }
        }
        i++;
    }
    return { suffix, prefix };
}

// BM单块匹配
function bmMatch(block, pattern, badCharTable, goodSuffixTable, currentOffset, results) {
    const patternLen = pattern.length;
    const blockLen = block.length;
    let i = 0;
    while (i <= blockLen - patternLen) {
        let j = patternLen - 1;
        while (j >= 0 && pattern.charAt(j) === block.charAt(i + j)) j--;
        if (j < 0) {
            results.push(currentOffset + i);
            i += patternLen;
        } else {
            const badCharShift = j - badCharTable[block.charCodeAt(i + j)];
            let goodSuffixShift = 0;
            if (j < patternLen - 1) {
                const suffixLen = goodSuffixTable.suffix[j + 1];
                goodSuffixShift = suffixLen > 0 ? j + 1 - suffixLen : patternLen;
                if (goodSuffixShift === patternLen) {
                    for (let r = j + 2; r < patternLen; r++) {
                        if (goodSuffixTable.prefix[patternLen - r]) {
                            goodSuffixShift = r;
                            break;
                        }
                    }
                }
            }
            i += Math.max(badCharShift, goodSuffixShift);
        }
    }
    return block.slice(Math.max(0, blockLen - patternLen + 1));
}

// 流式匹配主函数
function streamBMatch(inputPath, pattern, outputPath) {
    const patternLen = pattern.length;
    if (patternLen < 32 || patternLen > 4096) {
        throw new Error("模式串长度需在32-4096之间");
    }
    const badCharTable = buildBadCharTable(pattern);
    const goodSuffixTable = buildGoodSuffixTable(pattern);

    let leftover = '';
    let totalCharsRead = 0;
    const results = [];

    const readStream = fs.createReadStream(inputPath, { encoding: 'utf8', highWaterMark: 1024 * 1024 });

    readStream.on('data', (chunk) => {
        const combined = leftover + chunk;
        leftover = bmMatch(combined, pattern, badCharTable, goodSuffixTable, totalCharsRead - leftover.length, results);
        totalCharsRead += chunk.length;
    });

    readStream.on('end', () => {
        if (leftover.length >= patternLen) {
            bmMatch(leftover, pattern, badCharTable, goodSuffixTable, totalCharsRead - leftover.length, results);
        }
        fs.writeFileSync(outputPath, results.join('\n'), 'utf8');
        console.log("匹配完成，结果已写入文件");
    });

    readStream.on('error', (err) => console.error("读取文件出错:", err));
}

// 调用示例
streamBMatch('./big_numbers.txt', 'your_32_to_4096_digit_pattern', './match_positions.txt');

三、PowerShell 改进版非崩溃方案（一次性测试） #

PowerShell默认Select-String会加载全文件到内存导致崩溃，改用.NET的StreamReader流式读取，结合KMP算法避免内存溢出。

实现代码 #

param(
    [string]$InputFile = "big_numbers.txt",
    [string]$Pattern = "your_32_to_4096_digit_pattern",
    [string]$OutputFile = "match_positions.txt"
)

$patternLen = $Pattern.Length
if ($patternLen -lt 32 -or $patternLen -gt 4096) {
    Write-Error "模式串长度需在32-4096之间"
    exit 1
}

# 构建KMP前缀表
function Build-KMPTable {
    param([string]$pattern)
    $len = $pattern.Length
    $lps = New-Object int[] $len
    $currentLen = 0
    $i = 1
    while ($i -lt $len) {
        if ($pattern[$i] -eq $pattern[$currentLen]) {
            $currentLen++
            $lps[$i] = $currentLen
            $i++
        } else {
            $currentLen = $currentLen -ne 0 ? $lps[$currentLen - 1] : 0
            if ($currentLen -eq 0) {
                $lps[$i] = 0
                $i++
            }
        }
    }
    return $lps
}

$lps = Build-KMPTable -pattern $Pattern
$totalCharsRead = 0
$currentState = 0
$leftover = ""

$reader = New-Object System.IO.StreamReader($InputFile)
$writer = New-Object System.IO.StreamWriter($OutputFile)

try {
    $buffer = New-Object char[] (1024*1024)
    while (($charsRead = $reader.Read($buffer, 0, $buffer.Length)) -gt 0) {
        $combined = $leftover + (-join $buffer[0..($charsRead-1)])
        $leftover = ""

        $combinedLen = $combined.Length
        for ($i = 0; $i -lt $combinedLen; $i++) {
            while ($currentState -gt 0 -and $combined[$i] -ne $Pattern[$currentState]) {
                $currentState = $lps[$currentState - 1]
            }
            if ($combined[$i] -eq $Pattern[$currentState]) {
                $currentState++
            }
            if ($currentState -eq $patternLen) {
                $startPos = $totalCharsRead - ($combinedLen - $i - 1)
                $writer.WriteLine($startPos)
                $currentState = $lps[$currentState - 1]
            }
        }

        if ($combinedLen -ge $patternLen - 1) {
            $leftover = $combined.Substring($combinedLen - ($patternLen - 1))
        } else {
            $leftover = $combined
        }
        $totalCharsRead += $charsRead
    }
} finally {
    $reader.Close()
    $writer.Close()
}

Write-Host "匹配完成，结果已写入 $OutputFile"

四、一次性测试快速方案（PowerShell分块读取） #

临时测试可直接用Get-Content分块读取，结合字符串匹配（性能略逊于KMP/BM，但实现快速）：

$inputFile = "big_numbers.txt"
$pattern = "your_32_to_4096_digit_pattern"
$outputFile = "match_positions.txt"
$blockSize = 1000000
$totalChars = 0
$results = @()

Get-Content $inputFile -ReadCount $blockSize | ForEach-Object {
    $block = $_ -join ""
    $offset = $totalChars
    $index = 0
    while ($index -le $block.Length - $pattern.Length) {
        $matchIndex = $block.IndexOf($pattern, $index)
        if ($matchIndex -eq -1) break
        $results += ($offset + $matchIndex)
        $index = $matchIndex + 1
    }
    $totalChars += $block.Length
}

$results | Out-File $outputFile -Encoding utf8

内容的提问来源于stack exchange，提问作者Simon Reinhardt