题解 | #String Matching# 两种方法

• 分别使用暴力算法、KMP算法求解
• 在main()函数实现调用

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 //1、经典暴力算法 
int BF(string text, string pattern) {
    int sum = 0;
    for (int pos = 0; pos < text.length() - pattern.length() + 1; pos++) {
        int flag = 1;
        // 从 pos 开始，检查是否与 pattern 匹配
        for (int i = 0; i < pattern.length(); i++) {
            if (text[pos + i] != pattern[i]) {
                flag = 0;
                break;
            }
        }
        if (flag) sum++;
    }
    return sum;
}
// 2、KMP数组
int* getNext(string pattern) { // 使用 DP 求解 next 数组
    int* next = new int[pattern.length()];
    next[0] = -1;
    int i = 0, j =
                -1; // i为当前主串正在匹配的位置，也是 next 数组的索引
    while (i < pattern.length()) {
        if (j == -1 || pattern[i] == pattern[j]) next[++i] = ++j;
        else j = next[j];
    }
    return next;
}
int KMP(string text, string pattern) {
    int* next = getNext(pattern);
    int sum = 0, j = -1; // 初始化 j 为-1
    for (int i = 0; i < text.length(); i++) { //匹配text[i]
        while (j != -1 && text[i] != pattern[j + 1]) { //j+1？
            j = next[j]; // 回退，更新模式串指针
        }
        if (text[i] == pattern[j + 1]) { // 匹配成功，令j加1
            j++;
        }
        if (j == pattern.length() - 1) { // 完全匹配，说明找到了一个子串
            sum++;
            j = next[j]; // j 回退，继续匹配
        }
    }
    delete[] next; // 释放内存空间
    return sum;
}

int main() {
    string text, pattern;
    while (cin >> text >> pattern) {
        int sum;
        sum=BF(text, pattern);
        // sum=KMP(text,pattern);
        cout << sum << endl;
    }
    return 0;
}