模式匹配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