KMP算法详解：在字符串中查找子字符串的第一个位置

KMP算法：高效查找子字符串

KMP算法是一种高效的字符串匹配算法，用于在给定字符串 s 中查找子字符串 n 的第一个出现位置。与朴素的字符串匹配算法相比，KMP算法通过预处理子字符串 n 的信息，避免了不必要的字符比较，从而提高了效率。

Python代码实现pythondef kmp(s, n): m, i, j = len(s), 0, 0 nxt = get_next(n) while i < m and j < len(n): if j == -1 or s[i] == n[j]: i, j = i+1, j+1 else: j = nxt[j] if j == len(n): return i - j else: return -1

def get_next(n): nxt = [-1] * len(n) i, j = 0, -1 while i < len(n) - 1: if j == -1 or n[i] == n[j]: i, j = i+1, j+1 nxt[i] = j else: j = nxt[j] return nxt

测试用例pythonassert kmp('hello, world', 'world') == 7assert kmp('mississippi', 'issip') == 4assert kmp('abcdefg', 'xyz') == -1assert kmp('abcabcabc', 'abc') == 0assert kmp('abcabcabc', 'bcd') == -1

总结

本文介绍了KMP算法的基本原理和Python代码实现，并通过测试用例验证了算法的正确性。KMP算法是一种高效的字符串匹配算法，在实际应用中具有广泛的用途。