在本教程中,我们将研究识别文本中的模式。除了主要内容之外还会有一个子字符串。目的是确定子字符串在文本中出现的次数以及出现的位置。
当文本很大并且我们需要定位特定关键字或术语的出现时,这种模式查找方法非常有用。
在本节中,我们将讨论最基本的“Python 中的朴素字符串匹配算法”以及如何通过更好、更短的代码来改进它。
朴素算法简介
顾名思义,朴素算法是非常基本且易于实现的算法。这些算法使用最基本、最明显的策略来像孩子一样完成任务。
对于初学者来说,在转向更高效、更复杂的算法之前,这些方法是一个很好的起点。其中之一是基本的字符串搜索算法。在字符串匹配/模式查找算法中,它是最基本的。
该过程从逐个字母匹配字符串开始。它搜索主文本和子字符串中的第一个字符。如果匹配,则继续到两个字符串中的下一个字符。
如果字符在循环中的任何位置都不匹配,则循环被中断,并且从主文本字符串中的下一个字符重新开始循环。
实现简单的字符串搜索
1
2
3
4
5
6
7
8
9
10
11
12
|
def naive(txt,wrd): lt = len (txt) #length of the string lw = len (wrd) / 3length of the substring(pattern) for i in range (lt - lw + 1 ): j = 0 while (j<lw): if txt[i + j] = = wrd[j]: j + = 1 else : break else : print ( 'found at position' ,i) |
上面代码中的“naive”方法采用两个参数:txt(要从中查找模式的主字符串)和 ward(要搜索的模式)。
由于至少要保留子串的长度来匹配末尾,因此从 0 到(字符串长度-子串长度+1)进行循环。‘for’ 循环从字符串 (text[I]) 中提取每个字符。
然后有一个内部 while 循环,将该字符与子字符串中的下一个字符进行比较,直到整个子字符串匹配。如果没有发现,循环就会中断,并且接下来的迭代(如下一个字符)将从过程中删除。
当发现完整的子字符串时,while 条件被破坏,否则运行部分,并显示位置。另一种是在循环内,仅当 if 条件为 false 时才运行,而另一种则在 while 循环条件为 false 时执行。
让我们看看以下输入的输出:
naive( "AABAACAADAABAABA" , "AABA" ) |
输出结果如下:
found at position 0 found at position 9 found at position 12 |
结论
恭喜!您刚刚学习了如何实现朴素字符串搜索算法。希望你喜欢它!😇
喜欢该教程吗?无论如何,我建议您查看下面提到的教程:
感谢您抽出宝贵时间!希望你学到新东西!😄