题目1：实现一个高效的字符串匹配算法 问题描述： 用于在一个文本字符串中查找一个模式字符串的所有出现位置。 编写一个函数KMPSearch(string text, string pattern) c#

题目1：实现高效的字符串匹配算法通常可以使用Knuth-Morris-Pratt (KMP) 算法。该算法通过构建部分匹配表(Partial Match Table, PMT)，避免了对每个字符进行不必要的回溯，从而提高了搜索效率。

**KMP算法步骤**:
1. **创建部分匹配表**：对于pattern中的每一个前缀子串，计算最长公共前后缀长度，并存储到PMT数组中。如果某个子串的前缀和下一个字符不匹配，直接跳过当前PMT值对应的字符数，而非回溯整个模式串。
2. **主循环**：在text和pattern上进行双指针扫描（i和j）。当text[i]和pattern[j]相等时，i和j都加一；如果不等，根据PMT更新j，直到找到一个适合的位置继续匹配。
3. **返回结果**：记录下所有匹配的起始位置。当j等于pattern的长度，说明找到了一个完整的匹配，然后在text中移动i到下一个可能的位置，继续检查。

C#实现如下：

public class KMPSearch {
    private int[] PMT;

    public List<int> KMPSearch(string text, string pattern) {
        if (string.IsNullOrEmpty(pattern)) return new List<int>();

        // 初始化PMT
        PMT = BuildPMT(pattern);

        int j = 0;
        List<int> positions = new List<int>();
        for (int i = 0; i < text.Length; i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = PMT[j - 1];
            }
            if (text[i] == pattern[j]) {
                j++;
            }
            if (j == pattern.Length) {
                positions.Add(i - j + 1);
                j = PMT[j - 1]; // 移动到下一个可能的位置
            }
        }

        return positions;
    }

    // 辅助方法，生成部分匹配表
    private int[] BuildPMT(string pattern) {
        int[] PMT = new int[pattern.Length];
        int len = 0; // 当前最长匹配前缀
        for (int i = 1; i < pattern.Length; i++) {
            if (len == 0 || pattern[i] == pattern[len]) {
                len++;
                PMT[i] = len;
            } else {
                len = PMT[len - 1];
            }
        }
        return PMT;
    }
}

// 使用示例
KMPSearch search = new KMPSearch();
List<int> matches = search.KMPSearch("hello world", "world");