KMP算法在C#中有五种高效实现方式：一、手动构建next数组与匹配逻辑；二、用Span<char>避免内存分配；三、封装为支持多匹配的扩展方法；四、用MemoryPool<int>池化next数组；五、通过unsafe指针加速构建。
如果您需要在C#中实现高效的子串查找功能，而传统暴力匹配在长文本中性能不足，则KMP（Knuth-Morris-Pratt）算法可显著减少不必要的字符比较。以下是实现KMP算法的多种方式：
一、手动实现KMP核心逻辑（含next数组构建）
该方法完全自主编写KMP的两个关键部分：前缀函数（next数组）计算与主匹配过程，便于理解算法本质并支持自定义优化。
1、定义一个静态方法ComputeNext，接收模式串pattern，返回int[]类型的next数组；
2、遍历pattern，使用双指针i和j，初始j=0，i从1开始，若pattern[i]==pattern[j]则j++并赋值next[i]=j，否则当j>0时令j=next[j-1]继续回溯；
3、定义主匹配方法KmpSearch，接收text和pattern，先调用ComputeNext获取next数组；
4、使用指针i遍历text，指针j遍历pattern，若text[i]==pattern[j]则i++、j++；
5、若j达到pattern.Length，返回i-j作为首次匹配起始索引；
6、若不匹配且j>0，令j=next[j-1]；若j==0且仍不匹配，则i++；
7、遍历结束后未找到则返回-1。
二、使用Span<char>提升性能的无分配实现
该方法利用C# 7.2+的Span<char>避免字符串切片产生的内存分配，在高频或大文本匹配场景下降低GC压力。
1、将输入text和pattern分别转为ReadOnlySpan<char>>；
2、为next数组分配栈空间：Span<int> next = stackalloc int[pattern.Length]；
3、使用ref readonly Span<char>引用pattern，确保不触发复制；
4、在ComputeNext逻辑中全部基于Span索引操作，禁用string.Substring等分配操作；
5、主循环中用text.Slice(i, remaining)替代text.Substring(i)，但实际仅用索引比对；
6、所有字符访问均通过span[index]语法，保障零装箱与缓存友好性；
7、返回结果为int类型位置索引，不封装为IEnumerable<int>以避免迭代器开销。
三、封装为扩展方法并支持多匹配结果
该方法将KMP逻辑封装为string类型的扩展方法，提供简洁API，并内置全量匹配位置收集能力，适用于需获取所有出现位置的场景。
1、声明静态类StringExtensions，并定义public static IEnumerable<int> KmpFindAll(this string text, string pattern)；
2、内部校验text与pattern是否为null或pattern为空，空pattern按约定返回0到text.Length所有索引；
3、调用私有方法BuildNextArray生成next数组；
4、主循环中每次成功匹配后，记录当前位置i - pattern.Length + 1；
5、匹配成功后令j = next[j - 1]（而非归零），继续搜索重叠匹配；
6、使用yield return逐个输出索引，避免一次性分配List<int>；
7、调用示例：text.KmpFindAll("abc").ToArray()可直接获取全部起始位置数组。
四、基于Memory<char>与IMemoryOwner<int>的池化next数组实现
该方法面向高吞吐服务场景，复用next数组内存块，避免频繁堆分配，配合MemoryPool<int>.Shared实现对象池管理。
1、引入System.Buffers命名空间，声明private static readonly MemoryPool<int> s_pool = MemoryPool<int>.Shared；
2、在KmpSearch方法内请求IMemoryOwner<int> owner = s_pool.Rent(pattern.Length)；
3、通过owner.Memory.Span获取Span<int> nextSpan用于构建next数组；
4、匹配完成后立即调用owner.Dispose()将内存归还池中；
5、text与pattern仍为string，但内部比对逻辑使用AsSpan()转为ReadOnlySpan<char>；
6、整个生命周期内无new int[pattern.Length]语句；
7、next数组大小严格按pattern.Length申请，不预留冗余空间。
五、使用unsafe代码块加速next数组构建
该方法启用unsafe上下文，通过指针直接操作字符内存地址，消除边界检查开销，在超长pattern（如数万字符）构建next时获得可观加速。
1、在项目文件中启用<AllowUnsafeBlocks>true</AllowUnsafeBlocks>；
2、在ComputeNext方法前添加unsafe关键字，参数pattern改为string pattern；
3、使用fixed (char* p = pattern)固定pattern首地址，获取char* ptr = p；
4、用指针算术ptr[i]替代pattern[i]，j变量也以int*方式管理（如int* nextPtr = stackalloc int[n]）；
5、所有循环内比较使用*(ptr + i) == *(ptr + j)；
6、next数组填充使用*(nextPtr + i) = j；
7、主匹配循环同样采用fixed + 指针遍历text，跳过托管数组索引验证。
