字符串匹配常用算法

1 暴力匹配

思想：逐一匹配

时间复杂度：

实现：

  

   

    

     

    
    

     

      # -----------------------------------------
     
    
   

    

     

    
    

     

      # https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/?ref=lbp
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      def find_brute_force(pat, txt):
     
    
   

    

     

    
    

     

          """在txt中找到pat的匹配项，并返回txt匹配时第一个索引"""
     
    
   

    

     

    
    

     

          m, n = len(pat), len(txt)
     
    
   

    

     

    
    

     

          for begin in range(n - m + 1):
     
    
   

    

     

    
    

     

              match = 0
     
    
   

    

     

    
    

     

              while match < m:
     
    
   

    

     

    
    

     

                  if txt[begin + match] != pat[match]:
     
    
   

    

     

    
    

     

                      break
     
    
   

    

     

    
    

     

                  match += 1
     
    
   

    

     

    
    

     

              if match == m:
     
    
   

    

     

    
    

     

                  print("Pattern found at index ", begin)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      txt = "AABAACAADAABAAABAA"
     
    
   

    

     

    
    

     

      pat = "AABA"
     
    
   

    

     

    
    

     

      find_brute_force(pat, txt)
     
    
  
 

优化匹配：

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/123678151