字符串匹配算法

字符串匹配问题指的是从一个大字符串S中寻找是否包含小的串s，如果包含找到起始位置。或者说从主串中寻找模式串。
在牛客网上有该题：（串的模式匹配）
题目描述
对于两个字符串A，B。请设计一个高效算法，找到B在A中第一次出现的起始位置。若B未在A中出现，则返回-1。
给定两个字符串A和B，及它们的长度lena和lenb，请返回题目所求的答案。
测试样例
"acbc",4,"bc",2
返回：2

朴素的字符串匹配算法

朴素的字符串匹配算法也就是能直接想到的算法，将大字符串的每一个字符和小字符串做匹配，类似于小字符串是一个滑动窗口，每次滑动1，看是否相等。

class StringPattern:
    def findAppearance(self, A, lena, B, lenb):
        # write code here
        for i in range(lena-lenb+1):
            flag=0
            for j in range(lenb):
                if A[i+j]!=B[j]:
                    flag=1
                    break
            if flag==0:
                return i
        return -1

时间复杂度是O(m*n)。

KMP

通过设定一个next数组，当匹配失败时可以跳转到一定的位置继续比较。

class StringPattern:
   def getNext(self, A, lena):
       i=0
       j=-1
       next=[-1]
       while i<lena:
           if j==-1 or A[i]==A[j]:
               i+=1
               j+=1
               next.append(j)
           else:
               j=next[j]
       return next
   
   def findAppearance(self, A, lena, B, lenb):
       # write code here
       next=self.getNext(B,lenb)
       i=0
       j=0
       while i<lena and j<lenb:
           if j==-1 or A[i]==B[j]:
               if j==lenb-1:
                   return i-lenb+1
               i+=1
               j+=1
           else:
               j=next[j]
       return -1