Python中的KMP算法

阅读量：

文章结构概览

字符串匹配问题
- - 穷举方式的解决策略
  - - Python程序代码
  - KMP算法原理
  - - next数组的推导公式
    - Python程序代码
  - 穷举方式与KMP算法的差异分析
  - KMP算法的实际应用：PowerString问题
  - - Python程序代码

字符串查找问题

针对给定的文本字符串text与目标模式字符串pattern，需确定在文本字符串text中首次匹配到模式字符串pattern的具体起始位置。

暴力求解算法分析

Python代码

复制代码

    # 暴力求解
    def brute_force_search(ss, s):
    i = 0  # 当前匹配的原始字符串首位
    j = 0  # 模式串的匹配位置
    size = len(s)
    nlast = len(ss) - size
    while i <= nlast and j < size:
        if ss[i + j] == s[j]:  # 若匹配模式串位置后移
            j += 1
        else:  # 若不匹配，则对比下一个位置，模式串回溯到首位
            i += 1

全部评论 (0)

还没有任何评论哟~