一、主串和模式串：
假设在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。把主串的长度记作，模式串的长度记作
。因为是在主串中查找模式串，所以
。
二、暴力匹配算法/朴素匹配算法/BF(Brute Force)算法：
1、算法思想：
在主串中，检查起始位置分别是0、 1、 2···且长度为
的
个子串，看有没有跟模式串匹配的。
2、图示：
![]()
3、时间复杂度：
在极端情况下，每次都比对个字符，要比对
次，所以，这种算法的最坏情况时间复杂度是
。
三、RK(Rabin-Karp)算法：
1、算法思想：
通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（哈希冲突：当发现一个子串的哈希值跟模式串的哈希值相等的时候，只需要再对比一下子串和模式串本身即可）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
2、图示：
![]()
3、提高哈希算法计算子串哈希值的效率的方法：
假设要匹配的字符串的字符集中只包含K个字符，就用一个K进制数来表示一个子串，这个K进制数转化成十进制数，作为子串的哈希值。
而相邻两个子串s[i-1]和s[i]（i表示子串在主串中的起始位置，子串的长度都为m），对应的哈希值计算公式有交集，也就是说，可以使用s[i-1]的哈希值很快的计算出s[i]的哈希值。如果用公式表示的话，就是下面这个样子：
注意：这部分的计算，可以通过查表的方法来提高效率。事先计算好、 、 ……，并且存储在一个长度为的数组中，公式中的“次方”就对应数组的下标。当需要计算的次方的时候，就可以从数组的下标为的位置取值，直接使用，省去了计算的时间。
4、时间复杂度：
整个RK算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是。模式串哈希值与每个子串哈希值之间的比较的时间复杂度是
，总共需要比较
个子串的哈希值，所以，这部分的时间复杂度也是
。所以，RK算法整体的时间复杂度就是
。
