1.任务描述

       对给定两个字符串，编程实现字符串的查找，并找出p在s中出现的次数和出现的位置。并尝试能否将p在s中出现的位置高亮显示出来。（或者在s中高亮显示找到的字符串p；或者实现类似word中的“下一个”按钮功能），至少用两种算法实现；

       根据实验结果比较几种算法的优劣，尤其是时间复杂度和空间复杂度（给定sanguo.txt，对比各种算法在其中查找某个字符串的时间。

2.算法设计

2.1 BF算法：

       从主串的start位置开始与模式串进行匹配，如果相等，则继续比较后续字符，如果不相等则模式串回溯到开始位置，主串回溯到start+1位置，继续进行比较直至模式串的所有字符都已经比较成功，则匹配成功，或者主串所有的字符已经比较完毕，没有找到完全匹配的子串，则匹配失败。

图1  BF算法流程图

2.2 KMP算法：

       每当一趟匹配过程中出现字符不匹配时，不需要回退i指针，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续匹配过程。

图2 KMP算法流程图

3.程序实现

3.1 BF算法：

RED = '\033[31m'
END = '\033[0m'

from time import time_ns

if __name__ == '__main__':
    with open(r"sanguo.txt", "r", encoding="UTF-8") as fp:
        fileInfor = fp.read()
    position = []
    findInfor = input("输入查找信息：")
    start = time_ns()
    for i in range(0, len(fileInfor)):
        if findInfor == fileInfor[i:len(findInfor) + i]:
            position.append(i)
    end = time_ns() - start
    print("花费时间为：" + str(end)) 
    fileInfor = fileInfor.replace(findInfor, RED + findInfor + END)
    print(fileInfor)
    print("位置为：")
    print(position)

3.2 KMP算法：

from time import time_ns

RED = '\033[31m'
END = '\033[0m'

if __name__ == '__main__':
    with open("sanguo.txt", "r", encoding="UTF-8") as fp:
        infor = fp.read()
    myString = input("输入需要查找的单词：")
    myList = [-1, ]
    for i in range(1, len(myString)):
        tempString = myString[0:i + 1]
        for j in range(len(tempString), 0, -1):
            if tempString[0:j - 1] == tempString[len(tempString) - j + 1:len(tempString)]:
                myList.append(j - 1)
                break
    # print(myList)
    position = list()
    m = s = 0
    start = time_ns()
    while m < len(infor):
        if s == -1 or infor[m] == myString[s]:
            s += 1
            m += 1
        else:
            s = myList[s]
        if s == len(myString):
            position.append(m - s)
            s = 0
    end = time_ns() - start
    print("花费时间为:" + str(end))
    fileInfor = infor.replace(myString, RED + myString + END)
    print(fileInfor)
    print(position)

注：“sanguo.txt"文件为任意文本内容