字符串匹配算法

场景：字符串A为主串，字符串B为模式串，比较字符串B是否能够在字符串A中进行匹配？

匹配算法：BF算法和RK算法。

BF算法：（Brute Force）暴力匹配算法也叫朴素匹配算法，A为主串，B为字串。假定A字符串长度为n，B字符串长度为m，遍历A字符串从开始位置每次取m个字符的子串，字串数目= n - m + 1。然后比较字串与B是否一样，如果相同则结束。

BF算法时间复杂度 = 遍历的时间复杂度 * 比较的时间复杂度 = O(n - m + 1) * O(m) = O(m * n)

即可知BF算法优缺点：算法简单易懂，代码实现容易维护，对于字符串较短的场景基本都满足要求。但是如果字符串长度较长，这种算法的耗时就会急剧增加。

实际例子，java.lang.String.indexOf()代码如下：

RK算法：Rabin和Karp人名进行命名。BF算法有一个耗时点是子串进行比较时需要一个个字符进行比较，时间复杂度为O(m)。RK算法是先计算好 n - m + 1个子串的哈希值，然后比较子串和目标串的哈希值，由于都是整数只需要比较大小即可时间复杂度为O(1)。所以RK算法的耗时主要是哈希算法的耗时，计算n-m+1个子串的哈希值的时间复杂度=O(n)。

前面讲过好的哈希算法需要满足：1，散列冲突较少。2，散列函数的计算效率较高。

常见的哈希算法如设计 （a-z)26个字母的哈希算法。a-z分别对应十进制0-25

bbcd = 1 * 26^3 + 1 * 26 ^2 + 2 * 26 + 3。这就保证了不同的字符串哈希值肯定不同。如果字符串长度过长会导致整数溢出的场景，可能需要对哈希算法再进行设计。保证在不溢出的情况下，尽量减少哈希冲突。如果出现字符串不同，哈希值一样的情况，可以先获取哈希值相同的子串然后再比较子串与目标串是否完全一致。