Python 中的樸素字符串匹配算法：示例、特色和優缺點

當需要在字符串中查找輸入模式時，編碼人員和程序員會使用字符串匹配算法。 通常，在短字符串的情況下，python 程序員更喜歡使用簡單的方法，在這種方法中，程序檢查輸入字符串中的每個位置的查詢模式。 如果它匹配，它會給出一個帶有位置編號的輸出。

使用樸素字符串匹配算法的最大原因之一是它速度快並且產生了相當準確的結果。 此外，它不需要預處理。 無論如何，我們將在本文稍後階段討論這些優勢。 讓我們首先了解使用樸素方法進行模式搜索的算法。

樸素模式搜索算法

在樸素字符串模式搜索中，程序測試輸入模式 P [1……i] 在字符串 T [1……..m] 中的位置。

請注意，輸入文本或字符串的長度將始終大於或等於模式的長度。

這是針對不同編程語言的樸素模式搜索算法。

開始

pat = 圖案尺寸

str = 字符串大小

對於 i = 0 到 (str – pat)，做

對於 j = 0 拍，做

如果文本[i+j] ≠ 模式[j]，則

打破循環

完畢

如果 j == 帕特，那麼

將 i 的位置顯示為找到的模式

完畢

結尾

該算法在計算機科學中非常重要，因為它有助於將搜索結果作為輸出。

閱讀：你應該知道的人工智能算法類型

Python 上的樸素字符串匹配示例

這是一個在 python 代碼中使用樸素模式搜索方法的示例。

# 用於樸素字符串匹配的 Python 程序

# 搜索算法

定義搜索（P，T）：

X =長度（P）

Y =長度 (T)

# 一個循環將 P[] 一個一個移位 */

對於範圍內的i (X – Y + 1)：

j = 0

# 對於當前索引 i，檢查

# 用於模式匹配 */

對於範圍內的j (0, X)：

如果(txt[i + j] ! = P[j]):

休息

如果（j == X – 1）：

print (“在位置找到的圖案”, i)

# 驅動程序代碼

如果__name__ == '__main__'：

T = “升級DUBUPGRAABUPGRADEDU”

P = “升級”

搜索（P，T）

輸出：

在位置 0 找到的模式

在位置 17 找到的模式

解釋：第一個位置是第 0個位置。 由於模式“UPGRAD”首次出現在此處，輸出顯示該模式位於位置 0。

同樣，在位置 17 處發現了下一個模式。

樸素模式搜索的最佳案例

與兩種最壞情況不同，樸素模式搜索算法只有一種最佳情況。

最好的情況是模式文本中的第一個字符不在輸入字符串中。

例子：

T [] =“升級”；

P [] = “圖格拉”；

因此，匹配模式案例的數量為 O(n)。

樸素模式搜索的最壞情況

樸素的字符串搜索方法有兩種最壞的情況。

1. 當模式中的所有字符與輸入字符串中的字符相同時。

T [] = “EEEEEEEEEEEEEE”；

P [] = “EEE”；

1. 當模式中只有最後一個字符與輸入字符串不同時。

T [] = “EEEEEEEEEEED”；

P [] = “EEEED”；

在這種情況下，O(m*(n-m+1)) 中的比較次數。

樸素字符串匹配算法的特點

字符串匹配算法用於查找文本中給定模式的所有出現。

以下是該算法的主要特徵。

1. 在輸入文本中查找模式是最簡單的方法。 它一一檢查給定字符串中的所有字符。
2. 它找到精確的字符串匹配——無論是更多或更精確的模式出現。
3. 當有小文本時使用較多。 此外，它不需要任何預處理階段。
4. 這種搜索方法不會佔用額外的空間來工作和查找字符串中的模式。

另請閱讀： Python 中的數據結構和算法

樸素模式搜索的優勢

1. 樸素搜索方法不需要預處理階段，因為它的運行時間等於匹配時間。
2. 不需要額外的操作空間。
3. 模式與字符串的比較可以按任何順序進行。

樸素字符串匹配的缺點

樸素的字符串匹配方法只有一個缺點，那就是效率低下。 這是因為當它找到一個位置時，它不會再次使用它來尋找另一個位置。 它回到起點並再次尋找模式。 因此，它不再使用上一班次的信息。

結論

樸素字符串匹配算法是在給定文本中查找所述模式的位置的最優選方法，原因有多種，例如不需要預處理、沒有額外的操作空間等。但是，它不能用於更大的文本，因為其效率低下，無法更快地執行大型操作。

我們希望這篇文章能讓您對 Python 中的樸素模式搜索方法有一個很好的了解。 要了解此方法的用途並更廣泛地了解該主題，請與 upGrad 的專家聯繫。 我們為希望擴展技能的個人專門設計了課程。 今天就聯繫我們吧！

如果您有興趣了解更多關於人工智能、機器學習的信息，請查看 IIIT-B 和 upGrad 的機器學習和人工智能 PG 文憑，該文憑專為在職專業人士設計，提供 450 多個小時的嚴格培訓、30 多個案例研究和作業， IIIT-B 校友身份、5 個以上實用的實踐頂點項目和頂級公司的工作協助。