Python实现BF算法

一、题目要求

实现字符串模式匹配BF（Brute-Force）算法（基于链串也可以）。

函数功能：BF算法­——求模式串t在目标串s是否匹配

函数输入：目标串s、模式串t

函数输出：匹配成功：返回模式串t首次在s中出现的位置

                 匹配不成功：返回-1

二、思路：

借鉴网上C++思路写了python的实现：

1 子串t从头开始，依次与主串对比，匹配失败时子串从头开始，主串后移

2 一个循环三个判断

•         i和k(主串每次匹配的开头)的距离与j和开头的距离相同且j位于子串末尾——匹配成功
•         不断判断对应位置是否相同，相同向后遍历
•         一旦不同使主串后移，子串清0重新开始对比(如果一轮开始前主串剩余长度<子串长度直接匹配失败)

        

三、代码：

#!/usr/bin/python3
# author lzx


# python实现
def BF(s, t):
    i = 0
    j = 0
    k = 0
    flag1 = -1
    while (i < len(s) and j < len(t)):
        # 匹配成功
        if (i - k == j) and (j == len(t) - 1) and (s[i] == t[j]):
            flag1 = k
            break
        # s和t相等就继续向后匹配
        if s[i] == t[j]:
            i = i + 1
            j = j + 1
        # 不相等从k的位置开始匹配
        else:
            k = k + 1
            i = k
            j = 0
            # 假如s中所剩字符小于t中所剩字符
            if (len(s) - i) < len(t):
                flag1 = -1
                break
    return flag1


if __name__ == '__main__':
    s = input('输入目标串s：')
    t = input('输入模式串t：')
    flag = BF(s, t)
    if flag != -1:
        print('t在s的位置：', flag)
    else:
        print(flag, '匹配失败')