字符串匹配-Naive算法

字符串匹配算法

字符串匹配算法在生物信息学中应用广泛，在各种比对算法高频出现。
字符串\(S\)是将\(n\)个字符顺序排列而成的序列，\(n\)为其长度。 - 如果字符串的下标是\(1\)开始，S的第i个字符是\(S[i]\) - 如果字符串的下标从\(0\)开始，S的第i个字符是\(S[i-1]\)

字符串匹配就是给定文本字符串(String)是一个长度为\(n\)的数组\(S[1..n]\), 模式(Pattern)是一个长度为\(m\)且\(m<=n\)的数组\(P[1..m]\)，在string中寻找 pattern的过程。

Naive String Match

朴素的字符串匹配算法，也称为暴力匹配算法。

• 没有预处理
  
• 滑动窗口为1
  
• 时间复杂度\(O((n-m+1)m)\)
• 模式中的字符串比较顺序不限

def naive_match(partten, text):
    occurrences = []
    for i in range(len(text) - len(partten) +1):
        match = True 
        for j in range(len(pattern)):
            if text[i+j] != pattern[j]:
                match = False
                break
        if match:
            occurrences.append(i)
    return occurrences