数据结构(10)-字符串匹配
给定两个字符串S和T，判断模式串T是否是主串S的子串，如果不是返回-1，如果是则返回T在S中第一次出现的位置。
示例1：
字符串S: abcdefg；字符串T: cdef。返回2，即c的下标。
示例2：
字符串S: abcdefgh；字符串T: bce。返回-1。
BF算法
BF算法，即暴力(Brute Force)算法、暴风算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法的时间复杂度是O(m*n)。
我们以上述示例1为例进行拆解：
- 第一轮，将主串的第一个字母
a和模式串的第一个字母比较c比较，不匹配 - 第二轮，将主串的第二个字母
b和模式串的第一个字母比较c比较，不匹配 - 第三轮，将主串的第三个字母
c和模式串的第一个字母比较c比较，匹配 - 第四轮，将主串的第四个字母
d和模式串的第二个字母比较d比较，匹配 - 第五轮，将主串的第六个字母
e和模式串的第三个字母比较e比较，匹配 - 第六轮，将主串的第七个字母
f和模式串的第四个字母比较f比较，匹配，此时模式串已经遍历到最后一个字母，比较完成，可以得到结果，模式串T是主串S的子串，第一个位置即c的下标2。
代码实现如下：
int strStr(char * S, char * T) {
int hlen = (int)strlen(S);
int nlen = (int)strlen(T);
if (nlen == 0) {
return 0;
}
if (nlen > hlen) {
return -1;
}
int i = 0;
int j = 0;
while (i < hlen && j < nlen) {
if (S[i] == T[j]) {
if (j == nlen - 1) {
return i - nlen + 1;
}
// 如果相等、后移一位继续比较
i += 1;
j += 1;
} else {
// 如果不相等，则主串从这一轮开始的位置后移一位 模式串归零
i = i - j + 1;
j = 0;
}
}
return -1;
}
暴力算法最大的特点就是简单暴力，法如其名，但是这种算法的缺点就是效率低下。
RK算法
RK算法，全称是(Rabin-Karp)算法，它和BF算法的不同是，它比较的是字符串的哈希值(hash)，也就是不需要将字符串逐个比较，而是通过某种哈希算法将字符串的哈希值计算出来，然后直接对比哈希值。显然，对比字符串的哈希值要比逐个对比字符快的多，而且简单的多。RK算法最核心的点就是通过设计一个哈希函数得出字符串的哈希值。
设计哈希函数的时候，尽量保证在哈希冲突少的前提下算法能尽可能的简单一些。比如上述例子中，我们可以把a当做0，b当做1，c当做2......，然后把字符串的所有字符相加，相加结果就是它的哈希值，即cdef = 2 + 3 + 4 + 5 = 14。但是这个函数的计算出来值哈希冲突比较多，cefd、cfed、decf、dcef等这样的字符串哈希值都是一样的。所以需要对该函数进行优化。可以将把每一个字符串当成一个26进制数来计算，比如cdef = 2*(26^3) + 3*(26^2) + 4*26 + 5 = 37289。这样就能大幅度的减少哈希冲突。
因为函数存在哈希冲突，所以当我们比较到哈希值相等的这一组子串的时候还是需要将其与模式串挨个字符对比作为验证。
使用这种方式，虽然比较的过程变得简单高效了，但是计算哈希值却是增加了复杂度。考虑到每个子串都是有关联的，可以对其优化。我们先来看一下上述例子中主串abcdefg能够和模式串作对比的子串：abcd、bcde、cdef、defg，可以看出我们在计算bcde的哈希值的时候可以利用到abcd的结果。abcd = 0*(26^3) + 1*(26^2) + 2*26 + 3，而bcde = 1*(26^3) + 2*(26^2) + 3*26 + 4，即bcde = abcd * 26 + d - a*(26^4)。
int RK(char *S, char *P) {
unsigned int slen = (unsigned int)strlen(S);
unsigned int plen = (unsigned int)strlen(P);
unsigned int PHash = getHashValue(P);
char *FSChar = (char *)malloc(sizeof(char) * (plen + 1));
for (int i = 0; i < plen; i++) {
FSChar[i] = S[i];
}
FSChar[plen] = '\0';
unsigned int SHash = 0;
SHash = getHashValue(FSChar);
for (int i = 0; i < slen - plen; i++) {
if (SHash == PHash && isMatch(S, i, P, plen)) {
return i;
}
SHash = SHash * 26 + (S[i+plen] - 'a') - powl(26, plen) * (S[i] - 'a');
}
return -1;
}
相比于BF算法，RK算法的时间复杂度大大的提高了，虽然需要计算子串的哈希值，但是后续子串的哈希值是增量计算，所以总的时间复杂度为O(n)。RK算法的缺点就是哈希冲突，一旦出现哈希冲突，就会需要将子串和模式串挨个字符比较。所以设计一个合适的哈希函数是RK算法的重点。
BM算法
BM算法，全称是(Boyer-Moore)算法。BM算法是从模式串的尾部开始匹配，当不匹配的时候一次性可以跳过多个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。
BM算法中有两个核心规则：坏字符规则(bad-character shift)、好后缀规则(good-suffix shift)。
坏字符规则(bad-character shift)：当子串中的某个字符跟模式串的某个字符不匹配时，我们称子串中的这个失配字符为坏字符，此时模式串需要向右移动，这时候就分为两种情况，一种是坏字符包含在模式串之中，则移动模式串至模式串中最靠右的坏字符和主串的坏字符对齐，开始下一轮匹配；如果坏字符不包含在模式串之中，则直接把模式串移动到主串坏字符的下一位。坏字符针对的是子串。
以示例1为例，主串abcdefg中的前4个字符abcd和模式串cdef进行匹配，由于BM算法是从模式串的尾部开始匹配，首先第一个字符f和d不匹配，我们即认为d为坏字符，不难发现，模式串也存在字符d，此时我们就把模式串移动到字符d和主串的坏字符对齐，进行第二轮比较，进过字符的挨个比较，可以看出，这一次的子串和模式串是相等的，匹配完成。
那如果坏字符在模式串中不存在呢？下面我们在通过实例2来分析。abcdefgh的前3个字符abc和bce匹配，坏字符为c，移动模式串，bcd和bce匹配，坏字符为d，d在模式串中并不存在，所以将其移动到主串坏字符的下一个位置，即efg和bce进行匹配，此时坏字符为g，再次移动模式串，发现主串后续的子串长度已经不足，说明不存在匹配的子串。
代码实现：
// 从模式串获取坏字符
// 取到就返回坏字符的下标 如果不存在就返回-1
int getBadCharacterInPattern(char *P, char badChar, int bIndex) {
for (int i = bIndex - 1; i >= 0; i--) {
if (P[i] == badChar) {
return i;
}
}
return -1;
}
int BMBadCharacter(char *S, char *P) {
int slen = (int)strlen(S);
int plen = (int)strlen(P);
if (plen == 0 || slen <= plen) {
return 0;
}
int i = 0;
int j = plen - 1;
// 如果匹配到slen - plen位置，还是没有匹配到，后面剩下的子串长度就不够模式串的位置，返回-1
while (i <= slen - plen && j >= 0) {
// 模式串从后往前开始匹配
if (S[i+j] != P[j]) {
// 不相等 就去模式串找坏字符
int bIndex = getBadCharacterInPattern(P, S[i+j], j);
// 修改下一次比较的位置
if (bIndex == -1) {
i = i + j + 1;
} else {
i = i + j - bIndex;
}
j = plen - 1;
} else {
// 如果一直相等，且到了第一个字符 就说明匹配成功
if (j == 0) {
return i;
}
j -= 1;
}
}
return -1;
}
好后缀规则(good-suffix shift)：好后缀就是指模式串和子串当中相匹配的后缀。当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为 -1。好后缀针对的是模式串。
首先，我们来看一个例子：
主串：adccbecbbcb
模式串：cbbcb
在第一轮匹配中，cb就是好后缀。如果模式串的其他位置也包含与cb相等的串，那么我们就可以移动模式串，让其他位置cb和主串这个cb对齐进行下一轮匹配。如果模式串中不存在和cb相等的串，则需要判断模式串的前缀是否和好后缀的后缀相匹配，如果不匹配才能直接把模式串移动到主串好后缀位置之后，如果匹配则需要将模式串的前缀移动到和好后缀相匹配的位置。
好后缀规则不可以单独使用，需要和坏字符规则配合使用，比如：
主串：adefgecbbcb
模式串：cbbcb
第一轮比较就没有好后缀，此时就需要按坏字符的方法移动。配合的时候，需要分别计算出两种规则移动的距离，哪种距离更长，则使用哪种。
代码实现：
#define CHAR_MAX_COUNT 256 // 字符集
void getBadCharacterIndexs(char *P, int plen, int *badChars) {
for (int i = 0; i < CHAR_MAX_COUNT; i++) {
badChars[i] = -1;
}
for (int i = 0; i < plen; i++) {
badChars[P[i]] = i;
}
}
void getGoodSuffix(char *P, int plen, int *suffix, bool *prefix) {
int i, j, k;
for (i = 0; i < plen; i++) {
suffix[i] = -1;
prefix[i] = false;
}
for (i = 0; i < plen - 1; i++) {
j = i;
k = 0;//公共后缀子串长度(模式串尾部取k个出来，分别比较)
while(j >= 0 && P[j] == P[plen-1-k]) {
//与b[0,m-1]求公共后缀子串
j++;
k++;
suffix[k] = j+1;
//相同后缀子串长度为k时，该子串在b[0,i]中的起始下标
// (如果有多个相同长度的子串，被赋值覆盖，存较大的)
}
if (j == -1) {
//查找到模式串的头部了
prefix[k] = true;//如果公共后缀子串也是模式串的前缀子串
}
}
}
// 传入的j是坏字符对应的模式串中的字符下标
int moveIndexWithGoodSuffix(int badIndex, int plen, int *suffix, bool *prefix)
{
int i = plen - 1 - badIndex;//好后缀长度
if (suffix[i] != -1) {
// 找到跟好后缀一样的模式子串（多个的话，存的靠后的那个（子串起始下标））
return badIndex - suffix[i] + 1;
}
for(int j = badIndex + 2; j < plen; j++) {
// plen-j是好后缀的子串的长度，如果这个好后缀的子串是模式串的前缀子串
if(prefix[plen-j] == true) {
return j;
}
}
// 都没有匹配的，移动模式串长度
return plen;
}
int BMGoodSuffix(char *S, char *P) {
int slen = (int)strlen(S);
int plen = (int)strlen(P);
if (plen == 0 || slen <= plen) {
return 0;
}
int *badChars = (int *)malloc(sizeof(int) * CHAR_MAX_COUNT);
getBadCharacterIndexs(P, plen, badChars);
int *suffix = (int *)malloc(sizeof(int) * plen);
bool *prefix = (bool *)malloc(sizeof(bool) * plen);
getGoodSuffix(P, plen, suffix, prefix);
int i = 0, j, bcIndex, gsIndex;
while(i < slen - plen + 1) {
for (j = plen -1; j >= 0; j--) {
// 坏字符对应模式串中的下标是j
if(S[i+j] != P[j]) {
break;
}
}
if (j <= 0) {
return i;
}
bcIndex = j - badChars[S[i+j]];
gsIndex = 0;
if (j < plen - 1) {
gsIndex = moveIndexWithGoodSuffix(j, plen, suffix, prefix);
}
// 比较坏字符规则的移动步数和好后缀规则的移动步数 使用大的来移动 这样能减少次数
i = i + (bcIndex > gsIndex ? bcIndex : gsIndex);
}
return -1;
}
