def string_match(string, sub_str): 
 # 蠻力法字符串匹配 
 for i in range(len(string)-len(sub_str)+1): 
  index = i  # index指向下一個(gè)待比較的字符 
  for j in range(len(sub_str)): 
   if string[index] == sub_str[j]: 
    index += 1 
   else: 
    break 
   if index-i == len(sub_str): 
    return i 
 return -1 

if __name__ == "__main__": 
 print(string_match("adbcbdc", "dc")) 

__author__ = 'Wang' 
from collections import defaultdict 
def shift_table(pattern): 
 # 生成 Horspool 算法的移動(dòng)表 
 # 當(dāng)前檢測(cè)字符為c，模式長(zhǎng)度為m 
 # 如果當(dāng)前c不包含在模式的前m-1個(gè)字符中，移動(dòng)模式的長(zhǎng)度m 
 # 其他情況下移動(dòng)最右邊的的c到模式最后一個(gè)字符的距離 
 table = defaultdict(lambda: len(pattern)) 
 for index in range(0, len(pattern)-1): 
  table[pattern[index]] = len(pattern) - 1 - index 
 return table 
def horspool_match(pattern, text): 
 # 實(shí)現(xiàn) horspool 字符串匹配算法 
 # 匹配成功，返回模式在text中的開(kāi)始部分；否則返回 -1 
 table = shift_table(pattern) 
 index = len(pattern) - 1 
 while index <= len(text) - 1: 
  print("start matching at", index) 
  match_count = 0 
  while match_count < len(pattern) and pattern[len(pattern)-1-match_count] == text[index-match_count]: 
   match_count += 1 
  if match_count == len(pattern): 
   return index-match_count+1 
  else: 
   index += table[text[index]] 
 return -1 

if __name__ == "__main__": 
 print(horspool_match("barber", "jim_saw_me_in_a_barbershopp"))