题目:
有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = { a, b, d } ; 请找到模
式串在主串中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母;
一、BF算法
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法。
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。
BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法
思路：
1.分别利用计数指针i和j只是主串S和模式串T中当前正待比较的字符位置，初始值i = pos，j = 1;
2.若两个串均未比较到串尾即i<=S[0] && j<=T[0]，则执行以下操作：
S[i]和T[j]比较，若相等，则i和j分别指向串的下一个位置，继续比较后续字符；
若不相等，指针回退重新匹配， 从主串的下一个字符串(i = i - j + 2)起再重新和模式第一个字符(j = 1)比较;
3.如果j>T[0],也就是大于模式串的长度，说明匹配成功，返回 i-T[0],否则匹配成功返回-1；
/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
Status ClearString(String S)
{
S[0]=0;/* 令串长为零 */
return OK;
}
/* 输出字符串T。 */
void StrPrint(String T)
{
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
/* 输出Next数组值。 */
void NextPrint(int next[],int length)
{
int i;
for(i=1;i<=length;i++)
printf("%d",next[i]);
printf("\n");
}
/* 返回串的元素个数 */
int StrLength(String S)
{
return S[0];
}
//BF算法
int Index_BF(String S, String T,int pos){
int i = pos;
int j = 1;
while (i<=S[0] && j<=T[0]) {
if (S[i] == T[j]) {
i++;
j++;
} else {
//回溯，i指向上一次比较的下一个位置
i = i-j+2;
j = 1;
}
}
if (j>T[0]) {
return i-T[0];
} else {
return -1;
}
}
比方说，我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。
作为最简单、最暴力的字符串匹配算法，BF 算法的思想可以用一句话来概括，那就是，我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。我举一个例子给你看看，你应该可以理解得更清楚。
下载.jpeg
从上面的算法思想和例子，我们可以看出，在极端情况下，比如主串是“aaaaa…aaaaaa”（省略号表示有很多重复的字符 a），模式串是“aaaaab”。我们每次都比对 m 个字符，要比对 n-m+1 次，所以，这种算法的最坏情况时间复杂度是 O(n*m)。
尽管理论上，BF 算法的时间复杂度很高，是 O(n*m)，但在实[图片上传中...(下载.jpeg-b07085-1587487862139-0)]
际的开发中，它却是一个比较常用的字符串匹配算法。为什么这么说呢？原因有两点。
第一，实际的软件开发中，大部分情况下，模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候，当中途遇到不能匹配的字符的时候，就可以就停止了，不需要把 m 个字符都比对一下。所以，尽管理论上的最坏情况时间复杂度是 O(n*m)，但是，统计意义上，大部分情况下，算法执行效率要比这个高很多。
第二，朴素字符串匹配算法思想简单，代码实现也非常简单。简单意味着不容易出错，如果有 bug 也容易暴露和修复。在工程中，在满足性能要求的前提下，简单是首选。这也是我们常说的KISS（Keep it Simple and Stupid）设计原则
二、RK算法
RK 算法的全称叫 Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的。这个算法理解起来也不是很难。它其实就是刚刚讲的 BF 算法的升级版。
在BF 算法中，如果模式串长度为 m，主串长度为 n，那在主串中，就会有 n-m+1 个长度为 m 的子串，我们只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。
但是，每次检查主串与子串是否匹配，需要依次比对每个字符，所以 BF 算法的时间复杂度就比较高，是 O(n*m)。我们对朴素的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。
RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了（这里先不考虑哈希冲突的问题，后面我们会讲到）。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串比较的效率就提高了。
下载 (1).jpeg
这里解释一下哈希：
Hash (哈希). 一般中文也翻译做”散列”; 也可以直接音译”哈希”;
散列在开发中是常见手段! 比如大家常用的MD5 算法就是哈希算法;
哈希算法在安全方面应用是非常多,一般体现在如下这几个方面:
- 文件校验
- 数字签名
- 鉴权协议
设计哈希算法：
我们假设要匹配的字符串的字符集中只包含 K 个字符，我们可以用一个 K 进制数来表示一个子串，这个 K 进制数转化成十进制数，作为子串的哈希值
比如要处理的字符串只包含 a～z 这 26 个小写字母，那我们就用二十六进制来表示一个字符串。我们把 a～z 这 26 个字符映射到 0～25 这 26 个数字，a 就表示 0，b 就表示 1，以此类推，z 表示 25。
注意：不可以直接用ASC码. 因为如果使用ASC码时,计算数字过大. 容易导出类型溢出;所以,我们要设计一个规则. 将字母-'a'的值单纯字母的对应的数字;
image.png
我们拿127和274举例
s[i] = 1 ✖ 10^2 + 2✖10^1 + 7 ✖100
s[i+1] = 2 ✖ 10^2 + 7✖10^1 + 4 ✖100
s[i+1] = 10 ✖ (127 - 1✖10^2 ) + 4
s[i+1] = 10 ✖ (s[i] - 1✖10^2 ) + 4
s[i+1] 实现上是上一个s[i]去掉最高位数据,其余的m-1为字符乘以d进制. 再加上最后一个为字符得到;
274 = (127 - 1✖d^2 ) ✖ d + 4
所以主串分割后的哈希值:St[i+1] = (st[i] - d^2 * s[i] ) * d + s[i+m]
RK 算法的效率要比 BF 算法高，现在，我们就分析一下，RK 算法的时间复杂度到底是多少？
整个 RK 算法包含两部分，计算子串哈希值和模式串哈希值与子串哈希值之间的比较。第一部分，我们前面也分析了，可以通过设计特殊的哈希算法，只需要扫描一遍主串就能计算出所有子串的哈希值了，所以这部分的时间复杂度是 O(n)。
模式串哈希值与每个子串哈希值之间的比较的时间复杂度是 O(1)，总共需要比较 n-m+1 个子串的哈希值，所以，这部分的时间复杂度也是 O(n)。所以，RK 算法整体的时间复杂度就是 O(n)。
哈希冲突
哈希冲突我们都不陌生，当存在哈希冲突的时候，有可能存在这样的情况，子串和模式串的哈希值虽然是相同的，但是两者本身并不匹配。
实际上，解决方法很简单。当我们发现一个子串的哈希值跟模式串的哈希值相等的时候，我们只需要再对比一下子串和模式串本身就好了。当然，如果子串的哈希值与模式串的哈希值不相等，那对应的子串和模式串肯定也是不匹配的，就不需要比对子串和模式串本身了。
所以，哈希算法的冲突概率要相对控制得低一些，如果存在大量冲突，就会导致 RK 算法的时间复杂度退化，效率下降。极端情况下，如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)。但也不要太悲观，一般情况下，冲突不会很多，RK 算法的效率还是比 BF 算法高的。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//d 表示进制
#define d 26
//3.算出最d进制下的最高位
//d^(m-1)位的值;
int getMaxValue(int m) {
int h = 1;
for (int i = 0; i<m-1; i++) {
h*=d;
}
return h;
}
//为了杜绝哈希冲突. 当前发现模式串和子串的HashValue 是一样的时候.还是需要二次确认2个字符串是否相等.
int isMatch(char *S,int i,char *P,int m) {
int iS = i;
int iP = 0;
while (iS<m+i && iP<m) {
if (S[iS] != P[iP]) {
return 0;
}
iS++;
iP++;
}
return 1;
}
/*
* 字符串匹配的RK算法
* Author：Rabin & Karp
* 若成功匹配返回主串中的偏移，否则返回-1
*/
int RK(char *S, char *P) {
//1. n:主串长度, m:子串长度
int n = (int)strlen(S);
int m = (int)strlen(P);
unsigned int A = 0;
unsigned int St = 0;
for (int i = 0; i<m; i++) {
A = (d*A+(P[i]-'a'));
St = (d*St+(S[i]-'a'));
}
int hValue = getMaxValue(m);
for (int i=0; i<=n-m; i++) {
if (A == St) {
if (isMatch(S, i, P, m)) {
return i+1;
}
}
St = (St - (S[i]-'a')*hValue)*d+(S[i+m]-'a');
}
return -1;
}
int main(int argc, const char * argv[]) {
char *buf="abcababcabx";
char *ptrn="abc";
printf("主串为%s\n",buf);
printf("子串为%s\n",ptrn);
int index = RK(buf, ptrn);
printf("find index : %d\n",index);
return 0;
}
网友评论