模式比對BF、KMP、BM、Sunday

BF模式比對

參考介紹

最好情況的複雜度為O(n+m)；最壞情況的複雜度為O(n*m)

def strmatch(a,b):
    for i in range(len(a)):
        if len(a)<len(b):
            break
        index=i
        for j in range(len(b)):
            if a[index] == b[j]:
                index +=1
            elif a[index] !=b[j]:
                break
            if index-i==len(b):
                return i
    return False
a='abcdefgacd'
b='acd'
print(strmatch(a,b))

def strmatch(a,b):
    for i in range(len(a)):
        if b[0]==a[i]:
            if b==a[i:len(b)+i]:
                return i
    return False
a='abcdefgacd'
b='acd'
print(strmatch(a,b))

           

KMP模式比對

參考介紹 學習視訊

def dpnext(pat):
    dp=[0 for _ in range(len(pat))]
    for i in range(1,len(pat)):
        '''
        細節操作，dp[i]的值代表的其實就是從開頭有dp[i]個字元和最後的dp[i]個字元一緻
        如果要比較的話，其實就可以直接比較第i個字元與第dp[i-1]個字元是否相等，如果相等
        那麼dp[i]=dp[i-1]+1；不等的話也有兩種情況，如果首位相等則店鋪dp[i]=1
        否則的話就為0，而初始化的過程中就直接全部賦0，是以不用操作
        '''
        if pat[i]==pat[dp[i-1]]:
            dp[i]=dp[i-1]+1
        elif pat[i]==pat[0]:
            dp[i]=1
    dp.insert(0,-1)
    return dp[:-1]

def kmp(str,pat):
    next = dpnext(pat)
    i,j = 0,0
    while(i<len(str)):
        if str[i]==pat[j]:
            if j == len(pat) - 1:#j已經移動到了pat的最後且最後的字元也相等
                j = next[j]#之是以把j定位到這裡是因為他前面有next[j]個字元是相等的
                print("founf in {}".format(i - len(pat) + 1))#也可以選擇找到之後繼續查找列印
                # return i - len(pat) + 1 #可以選擇找到第一個就傳回
            else:
                i,j =i+1,j+1
        else:#之是以把j定位到這裡是因為他前面有next[j]個字元是相等的
            j=next[j]
        if j==-1:#例子abceabcd，abcd就可以了解了
            i, j = i + 1, j + 1
# print(kmp('abcdabcaaeabcdabcaa','abcdabcaa'))
print(kmp('abceabcd','abcd'))
           

BM模式比對

參考介紹   

Sunday 算法

參考介紹

參考文獻：

BF算法

KMP算法

BM算法

Sunday 算法

https://zhuanlan.zhihu.com/p/74885159