字符串樸素匹配算法的 C++ 實現與解析

算法概述

樸素字符串匹配（Naive String Matching）是最直觀的模式匹配算法。其核心思想是：在主串的每一個位置嘗試與模式串逐字符比對，一旦發現不匹配即移至主串下一位置重新開始，直到模式串完全匹配或主串遍歷結束。

算法流程

1. 外層循環遍歷主串 a 的每個起始位置 tarindex。
2. 內層循環從該位置開始，依次比較主串與模式串 b 的對應字符。
3. 若所有字符均匹配（即模式串遍歷結束），返回當前起始索引。
4. 若中途不匹配，跳出內層循環，外層索引 tarindex 遞增，繼續下一輪嘗試。
5. 若主串遍歷完畢仍未找到匹配，返回 -1。

C++ 代碼實現

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int index(char *a, char *b) {
    int tarindex = 0;
    while (a[tarindex] != '\0') {
        int tarlen = tarindex;
        int patlen;
        for (patlen = 0; b[patlen] != '\0'; ++patlen) {
            if (a[tarlen++] != b[patlen]) {
                break;
            }
        }
        if (b[patlen] == '\0') {
            return tarindex; // 匹配成功
        }
        ++tarindex;
    }
    return -1; // 匹配失敗
}

int main() {
    char *a = new char[1000];
    char *b = new char[1000];
    gets(a);
    gets(b);
    cout << "第 " << index(a, b) << " 個位置" << endl;
    delete[] a;
    delete[] b;
    return 0;
}

複雜度分析

• 時間複雜度：最壞情況 O(m×n)，其中 m 為主串長度，n 為模式串長度。例如主串 "AAAAA...A"，模式串 "AAAAB"。
• 空間複雜度：O(1)，僅使用常數額外空間。

優化方向

樸素匹配在大數據量下效率較低，實際應用中常采用 KMP、Boyer-Moore 或 Sunday 等算法，通過預處理模式串跳過不必要的比對，將時間複雜度降至 O(m+n)。