用DEV-C++实现字符串应用算法：用BF和KMP算法实现两个字符串的模式匹配

在DEV-C++环境中，实现字符串的模式匹配通常会涉及到Brute Force (BF)暴力搜索算法和Knuth-Morris-Pratt (KMP)算法，它们都是用于查找文本串中是否存在给定模式串的高效算法。

**1. Brute Force (BF)暴力搜索算法：**
BF是最基础的模式匹配方法，它从文本的第一个字符开始逐个比较，如果当前字符与模式串的当前字符匹配，就继续下一位；如果不匹配，则向前移动文本字符直到找到下一个匹配位置。这种方法的时间复杂度较高，为O(nm)，其中n是文本串长度，m是模式串长度。

**2. Knuth-Morris-Pratt (KMP)算法：**
KMP算法通过构建模式串的失配函数（也称为部分匹配表），提前预处理模式串，避免了不必要的回溯操作。当遇到不匹配的情况时，会根据部分匹配表直接跳过已经匹配过的字符，减少比较次数。KMP算法的时间复杂度优化到了O(n + m)，比BF更快。

在DEV-C++中实现这两种算法，你可以：

- 对于BF，可以手动编写循环结构，对比每个字符。
- 对于KMP，需要先计算失配函数，然后在主循环中利用这个函数进行跳跃。

以下是简单的步骤概述：
1. **BF实现：**
- 定义两个指针，分别指向文本和模式串的开头。
- 循环遍历，逐个字符对比，直到找到匹配或完成遍历。
- 使用`if(text[i] == pattern[j])`检查字符是否相等，不等则移动较长的那个。

2. **KMP实现：**
- 编写函数计算失配函数表。
- 主循环中，用`while(i != 0 && text[i] != pattern[j])`代替直接比较，根据失配函数表调整指针位置。

#include <iostream>
#include <string>

// KMP算法部分匹配表生成函数
void compute_lps_table(const std::string& pattern, int lps[], int len) {
    int i = 1;
    lps[0] = 0;
    while (i < len) {
        if (pattern[i] == pattern[lps[i]])
            lps[i+1] = lps[i] + 1;
        else
            lps[i+1] = 0;
        i++;
    }
}

int main() {
    // ... (读取文本串text和模式串pattern)
    int lps[m];
    compute_lps_table(pattern, lps, pattern.length());

    int i = 0, j = 0;
    while (i < text.length()) {
        if (j < pattern.length() && text[i] == pattern[j])
            i++, j++;
        else if (j > 0)
            j = lps[j-1];
        else
            i++;
    }

    if (j == pattern.length())
        std::cout << "Pattern found!";
    else
        std::cout << "Pattern not found.";

    return 0;
}