字符串匹配（string matching）也称字符串查找(string searching)或模式匹配(pattern matching)。是计算机应用中最基本的操作之一。
假设有两个串
其中t、p都是字符。字符串匹配就是在t中查找与p相同的子串的过程。T称为目标串，p称为模式串。
串匹配算法设计的关键是怎样选择开始比较的字符对，如果发现不匹配后，下一步怎么做。针对这个问题形成了不同的处理策略，下面先主要介绍朴素匹配算法。
朴素字符串匹配算法
最简单的朴素匹配算法是采用直观可行的策略，从左到右逐个字符匹配，发现不匹配时，转去考虑目标串里的下一个位置是否与模式串匹配。其匹配过程如
如下匹配算法，返回模式字符串首次出现的位置。
defbruteforcestringmatch(pstr,tstr):
pstr_length=len(pstr)
tstr_length=len(tstr)
for i in range(0,tstr_length-pstr_length+1): #最后一轮匹配从cmpstr_length-srcstr_length开始
if pstr == tstr[i:pstr_length+i]:
return i
return -1
if语句实际上也是一个循环等价于
j=0
whilej<=pstr_length and pstr[j]==tstr[i+j]:
j+=1
if j== pstr_length:
return i
这种匹配算法是非常简单的，但是效率比较低，主要是因为匹配中遇到一对字符不同时，模式串将右移一个字符位置，随后的匹配回到模式串的开始，也回到目标串中前面的下一个位置，从哪里再次由模式串开始位置开始比较。
这种算法最坏的情况是每一趟比较都在模式串的最后遇到了字符不匹配的情况，在每次移动模式之前，算法需要做m次（模式长度）比较，而这种匹配总共需要做n-m+1次尝试，因此总的比较次数为m×(n-m+1)。所以时间复杂度为O(n×m)。
测试用例
>>>bruteforcestringmatch('stc','stc')
0
>>>bruteforcestringmatch('stc','abtcstdaastcstd')
9
>>>
朴素算法没有充分利用字符串的特点，也没有尽可能地利用前面已经做过的字符比较中得到的信息，任意两次字符比较都认为是相互无关的。实际上各种改进算法都利用了字符串本身的一些特点，从而设计出了高效串匹配算法，如KMP算法、boyer-moore算法。
boyer-moore算法
该算法比较的时候是从右至左，即开始的时候算法把模式和文本的开头字符对齐，如果第一次失败了，把模式向右移，只是每次尝试过程中的比较才是从右至左的。它的一个简化版算法称为horspool算法。
它的基本思想是，如果遇到一个不匹配的字符时，需要把模式右移（右移尽可能大，而又没有错过文本中一个匹配子串的风险），至于移动的步数取决于对齐后模式最后一个字符对应的文本字符c，这样会出现下面4种情况：
• 如果模式中不存在c，则模式串需要移动，移动的安全步数就是它的全部长度m。
• 如果模式中存在c，但不是模式的最后一个字符，则模式串需要移动，移动的安全步数是模式最右边的c和文本中的c对齐。
• 如果c是模式的最后一个字符，但是在模式的其他m-1个字符中不包含c，且模式与文本子串不匹配，则模式串需要移动，移动的步数等于m
• 如果c恰好是模式的最后一个字符，而且在模式的前m-1个字符中也包含c，但模式与文本子串不匹配，则模式移动到模式前m-1个子串中最右边的c和文本中的c对齐。
总结上述情况，我们不难发现如果c不包含在模式的前m-1个字符中，则移动的距离为模式长度m，在其他情况下，移动的距离为模式前m-1个字符中最右边的c到模式最后一个字符的距离。
因此我们以文本中所有可能遇到的字符为索引，创建一个辅助哈希表结构或关联数组。预先将每次移动的距离存放在这个结构中，每次比较时，如果需要移动，根据c就可以决定移动模式的步数了。如对于模式barber，文本字符串中如果存在a，由于a包含在模式串中，所以当a与模式右对齐的时候，可以放心地向右移动4个字符再对齐；如果文本字符串中存在b，同理可以放心地向右移动2个字符；如果文本字符串中存在c，因为模式串中不包含c，所以模式串需要向右移动6个字符，….。即除了e、b、r、a对应的值分别为1、2、3、4外，辅助表中其他字符对应值为6。
以文本字符串中只包含小写字母为例，在给定一个模式下，每个字符对应的移动距离存储表结构为
def shifttable(p):
m=len(p)
ptable=[m]*26 #初始化，存储字母序每个字母对应的移动步数
for j in range(0,m-1): #前m-1个字符
ptable[ord(p[j])-97]=m-1-j #下标依次对应a\b\c\d…
return ptable
测试用例
>>> p='barber'
>>> shifttable(p)
[4, 2, 6, 6, 1, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,3, 6, 6, 6, 6, 6, 6, 6, 6]
>>>
则horspool的实现算法为
def horspoolmatching(p,t):
hashtable=shifttable(p)
lenp=len(p)
lent=len(t)
i=lenp-1 #比较开始字符下标
while i<=lent-1:
k=0
while k<=lenp-1 and p[lenp-1-k]==t[i-k]: #从右至左逐个字符比较
k=k+1
if k==lenp:
return i-lenp+1
else:
i=i+hashtable[ord(t[i])-97] #移动步长
return -1
该算法的最差效率是O(mn)。
测试用例
>>>horspoolmatching('barber','barbbarberb')
4
>>> horspoolmatching('b','ab')
1
>>>
>>> horspoolmatching('b','ad')
-1
网友评论