问题陈述：给您一个字符串“ s”和一个模式“ p”。您需要查找字符串“ s”中是否存在模式。
通常我们可以用蛮力方法解决这个问题。即比较一个字母到另一个字母，直到找到子模式或到达字符串结尾。
可以如下所示：
上述方法效率不高。因此，我们选择一种有效的方法来解决此问题。
共有3种模式匹配算法。 KMP是其中的第一个算法。
在本教程中，我们将看到如何使用KMP算法求解。
与接下来的2种算法相比，KMP算法有点复杂/难以理解。我已确保该说明易于理解和遵循。
KMP算法包含2个部分：
- 部分匹配表
- 字符串匹配
该算法的高级工作：
通过某种机制[我们将在下一步中查看]，我们创建部分匹配表。该表将帮助我们在不匹配时跳过字符数。从而消除，检查所有字符。
-
创建部分匹配表
部分匹配表是最长适当前缀和适当后缀的字符的长度。
现在什么是适当的前缀和适当的后缀？
我们将在下面查看它：
正确的前缀：
它是除最后一个字符以外的所有字符的组合。前缀将按从左到右的顺序排列。
例如：
对于字符串“ 美国广播公司D”，
正确的前缀为：
A
AB
美国广播公司
我们不能将“ D”设置为“ 美国广播公司D”，实质上是将其设置为原始字符串。
正确的后缀：
它是除第一个字符外的所有字符的组合。后缀将按从右到左的顺序排列。
例如：
对于字符串“ 美国广播公司D”
正确的后缀将是：
D
光盘
BCD
同样，我们不能将“ A”设置为“ 美国广播公司D”，本质上使其成为原始字符串。
既然我们已经了解了什么是适当的前缀和适当的后缀，我们将构建一个部分匹配表[PMT]。
将为“模式”而非“字符串”创建PMT。
考虑模式“ ABABAB”。
由于有6个元素，因此PMT的长度将为6。
现在填充a [0]，对于a [0]，我们专注于“ a”。
因为只有1个元素，所以适当的前缀= 0，适当的后缀=0。因此a [0] = 0。
现在让我们填写a [1]，对于a [1]，我们专注于“ ab”。
这里适当的前缀= a，适当的后缀= b。由于没有匹配的字符，因此a [1] = 0。
现在填写a [2]，对于a [2]，我们专注于“ aba”。
这里适当的前缀= a，适当的后缀= a。由于存在1个匹配项，因此长度为1个字符，a [2] = 1
现在让我们填写a [3]，对于a [3]，我们关注“ abab”。
这里适当的前缀= a，ab，aba，适当的后缀= b，ab，bab。因为有1个匹配项，并且长度为2个字符，所以a [3] = 2。
现在让我们填写a [4]，对于a [4]，我们关注“ abab”。
这里适当的前缀= a，ab，aba，abab适当的后缀= b，ba，aba，baba。因为有1个匹配项，并且长度为3个字符，所以a [4] = 3。
现在填写[5]，对于[5]，我们专注于“ ababab”。
此处适当的前缀= a，ab，aba，abab，baba适当的后缀= b，ab，bab，abab，babab。因为有1个匹配项，并且长度为4个字符，所以a [5] = 4。
因此，我们最终的PMT将如下所示：
我们来2nd算法的一部分。在字符串中搜索模式。
要搜索字符串，请按照以下步骤操作：
第1步：取2个变量i和j
i =字符串[str [0]]
j =模式[0]
步骤2：比较str [i]和pattern [j + 1]<- important
- 如果找到匹配项，则增加I和j的索引。
- 如果不匹配，请按照PMT将j移至该位置。
- 如果j = 0，则递增i索引。
现在，我们将借助一个示例来测试上述步骤：
字符串= ababcacabababacadcad
在这里，如果您观察到，我们将从1开始字符串的索引，并且模式索引也为1。
我们将逐步看到算法的工作。
初始表如下：
根据算法，将str [i]与模式[j + 1]匹配。
即模式为[0 + 1]的str [1]如下所示：
这是一场比赛。因此增加“ i”和“ j”。
现在str [2] pattern [2]已经匹配了，继续前进。
现在str [3] pattern [3]已经匹配了，继续前进。
现在str [4] pattern [4]已经匹配了，继续前进。
现在str [5] pattern [5]不是匹配项。
现在我们来看PMT [5]，它是4。因此将j移到4日 位置再次不匹配。
现在再次在索引4处看到PMT，在索引4处，该值为2。因此，将“ j”移到2索引处，同样存在不匹配的情况。
现在，我们检查PMT中索引2处的值。它是0。
因此，将“ j”移动到0并将“ i”移动1作为belwo：
同样，str [6]与pattern [1]匹配
Str [7]与pattern [2]不匹配
现在检查PMT的索引2处的值为0。
在此再次将“ j = 0”和i移至下一个值。
现在再次检查：
Str [8] ==模式[1]
Str [9] ==模式[2]
Str [10] ==模式[3]
Str [11] ==模式[4]
Str [12] ==模式[5]
Str [13] ==模式[6]
因此，我们得到了子字符串。
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
