使用kmp算法匹配字符串来查找文件(java版本)-2

原创

cg错过

修改于 2020-12-02 09:50:20

5960

修改于 2020-12-02 09:50:20

文章被收录于专栏：程序笔记程序笔记

前言

接上篇文章, 这里完成改文章的后部分, 以python编写的版本

正文如下

同时，我也对原先写的python代码进行了修改，使用KMP算法

python实现KMP算法代码

其python实现的KMP算法核心代码如下

def kmpSearchStrByStr(totalStr, strSearch, kmpTable):

    #kmp算法查找
    #返回字符串中包含搜索串的个数

    listSearch = list(strSearch)
    listTotal = list(totalStr)

    s = 0
    t = 0
    existCount = 0
    while((s < len(listSearch)) & (t < len(listTotal))):
        if(listSearch[s] == listTotal[t]):
            if((s + 1) != len(listSearch)):
                s+=1
                t+=1
            else:
                existCount+=1
                if((len(listTotal) - (t + 1)) >= len(listSearch)):
                    s = 0
                    t+=1
                else:
                    break;
        elif(s == 0):
            s = 0
            t+=1
        else:
            s = s - (s - kmpTable[(s - 1)])
        if((t + 1) >= len(listTotal)):
            break
    #print(existCount)
    return existCount



def getKMPtable(strSearch):

    #获取kmp的部分匹配数值表
    #但得先获取字符串所有可能长度的最大公告元素长度，将其存放到int数组中返回

    intTablesLength = len(strSearch)
    kmpTable = []

    for i in range(intTablesLength):
        strItem = strSearch[0 : i + 1]
        intMaxPublicNum = getMaxPublicNum(strItem)
        kmpTable.append(intMaxPublicNum)

    #print(kmpTable)
    return kmpTable


def getMaxPublicNum(strItem):

    #获取前缀和后缀，并最终对比得到最大的公共元素长度,并返回

    intMaxPublicNum = 0
    intItemLength = len(strItem)

    listFront = []
    listBack = []

    for i in range(intItemLength - 1):
        listFront.append(strItem[0 : i + 1])

    for i in range(intItemLength, 1, -1):
        listBack.append(strItem[i - 1 : intItemLength])

    n = -1
    for i in range(intItemLength - 1):
        if(listFront[i] == listBack[i]):
            n = i
    if(n != -1):
        intMaxPublicNum = len(listFront[n])

    #print(intMaxPublicNum)
    return intMaxPublicNum