Python算法：Brute-Force算法查找字元串子串位置

Brute-Force算法，

簡稱為 BF算法，是一種簡單樸素的模式比對算法，常用于在一個主串 S 内查找一個子串 T 的出現位置。

它的核心思想與操作是：

對于給定的主串 S 與子串 P ，主串 S 的長度為 N，子串 T 的長度為 M ；

首先，将 S[1] 和 T[1] 進行比較；

若相等，則再比較 S[2] 和 T[2] ，一直到 T[M] 為止；

若 S[1] 和 T[1] 不等，則 T 向右移動一個字元的位置，再依次進行比較；

"""
  0 1 2 3 4
S a c b c d
T c d
s = 0 t = 0

S a c b c d
T   c d
s = 1 t = 0

S a c b c d
T   c d
s = 2 t = 1

S a c b c d
T     c d
s = 2 t = 0

S a c b c d
T       c d
s = 3 t = 0

S a c b c d
T       c d
s = 4 t = 1
"""      

代碼實作

def searchIndex(S, T):
    s, t, pos = 0, 0, 0
    S_len = len(S)
    T_len = len(T)

    while (s < S_len and t < T_len):
        print(s, t)
        if S[s] == T[t]:
            s += 1
            t += 1
        else:
            pos += 1
            s = pos
            t = 0
            
    if t == T_len:
        return pos
    else:
        return -1
        

print(searchIndex("abdabc", "abc"))
"""
0 0
1 1
2 2
1 0
2 0
3 0
4 1
5 2
3
"""


      

BF算法 在主串和字串比對失敗時，主串進行的回溯操作會影響效率，回溯之後，主串與字串有些部分比較是沒有必要的。這種簡單的丢棄前面的比對資訊是 BF算法 之是以效率低效的一個重要因素。

參考：

【資料結構與算法】動畫：什麼是 BF 算法 ？