字符串匹配問題指的是從一個(gè)大字符串S中尋找是否包含小的串s吮螺，如果包含找到起始位置》ィ或者說從主串中尋找模式串宠进。
在牛客網(wǎng)上有該題：（串的模式匹配）
題目描述
對于兩個(gè)字符串A藐翎，B材蹬。請?jiān)O(shè)計(jì)一個(gè)高效算法，找到B在A中第一次出現(xiàn)的起始位置吝镣。若B未在A中出現(xiàn)堤器，則返回-1。
給定兩個(gè)字符串A和B末贾，及它們的長度lena和lenb闸溃，請返回題目所求的答案。
測試樣例
"acbc",4,"bc",2
返回：2
樸素的字符串匹配算法
樸素的字符串匹配算法也就是能直接想到的算法拱撵，將大字符串的每一個(gè)字符和小字符串做匹配辉川，類似于小字符串是一個(gè)滑動窗口，每次滑動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
時(shí)間復(fù)雜度是O(m*n)。
KMP
通過設(shè)定一個(gè)next數(shù)組集索，當(dāng)匹配失敗時(shí)可以跳轉(zhuǎn)到一定的位置繼續(xù)比較寸齐。
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
