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 个以上实用的实践顶点项目和顶级公司的工作协助。