字符串匹配
假设有两个串s和p，字符串匹配就是在s中查找与p相同的子串的操作。将s称为目标串，p称为模式串。
BF
BF(Brute Force)算法又称为暴力匹配算法。将p与s的所有的子串进行匹配。最坏情况O(m*n)。
// return: first match index of s
int bf_match(char const * s, char const * p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
s_ind = s_ind - p_ind + 1;
p_ind = 0;
}
}
return p_ind == p_len ? s_ind : -1;
}
KMP
Knuth-Morris-Pratt字符串查找算法，简称为 “KMP算法”由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表。
Part 1
定义：绿色为SP匹配部分；红色为SP不匹配部分，此时的下标S[j]，P[i]，并且P[0:i-1] == S[j-i:j-1]。
bf算法的最大问题是：不会跳过无意义的步骤。如下图，在S[4]:e和P[4]:f匹配失败后，P[0]:a依然和S[1:3]依次进行匹配，做无用功。
结论1：匹配部分长度大于0(i>0)，如果P[0]在当前P[0:i-1]只出现一次，那么去匹配P[0]和S[j]；匹配部分长度等于0(i=0)，P[0] != S[j]，那么去匹配P[0]和S[j+1]。
Part 2
如下图，与结论1相反，在匹配部分出现多次P[0]:a是P[2]和P[4]，在S[6]:e和P[6]:f处匹配失败。
如下图，如果将P[0]:a与S[2]:a匹配，会在P[1]:b和S[3]:c处匹配失败，那么现在的情况又回到了结论1，将会进行P[0]:a与S[3]:c匹配，一样会失败。所以，这样的匹配会进行多次的无用功。在S[6]:e与P[6]:f匹配失败时就可以观察到P[0]:a与S[2]:a匹配最终一定会失败的，这个信息是在P[6]:f匹配失败时通过P串就能获得的，并不需要S串。
如下图，如果将P[0]:a与S[4]:a匹配，P[1]:b和S[5]:b也是匹配的，在S[6]:e与P[6]:f匹配失败时就可以观察到P[0]:a,b与S[4]:a,b匹配，这个信息是在P[6]:f匹配失败时就能获得的，并不需要S串。至于P[2]和S[6]是否匹配需要进行，不能单靠P[6]:f匹配失败时的P串获得这个信息。
如上图，这个匹配方法相比于bf跳过了P[0]与S[1:5]的比较，P[0]:a,b与S[4]:a,b是不需要匹配的，直接进行P[2]:a与S[6]:e的匹配，S串不进行回溯，P串进行短回溯。重点是如何找到这样的位置进行匹配：
∵ S[6]:e != P[6]:f
∴ S[0:5] == P[0:5]
export 0 <= n <= 4
if S[0:n] == P[0:n] && S[5-n:5] == P[0:n]
then P[0:n] == P[5-n:5]
结论2：P[i]匹配失败，i > 1 && 0 <= n <= i-2，如果存在P[0:n] == P[i-1-n:i-1]，就是P[0:i-1]存在一个前缀和后缀是相同的，那么进行P[n+1]与S[j]匹配。
为什么是P[n+1]？观察上图，n == 1，前缀P[0:1]的长度为2，需要和S[6]进行匹配的P的下标也是2，都刚好是n+1。结论是，如果存在前缀，则进行P[前缀长度]和S[j]的匹配。
Part 3
如上图，根据结论2会出现下图两种情况都满足。
按照从S左到右的匹配顺序，不应该错过P[0]与S[2]对齐时的P[4]与S[6]的匹配，直接进行P[0]与S[4]对齐时的P[2]与S[6]的匹配。在多种情况时，应该选择P[0]与S[最小能够对齐的下标]进行对齐。
结论3：应该选择满足 结论2 并且是最长的相同前后缀。
观察上图，在P[0]与S[2]对齐的匹配失败后，会自然落到P[0]与S[4]对齐的情况。
Part 4
基于以上结论，在P[i]和S[j]在匹配失败后，S串不回溯，P串回溯到i等于P[0:i-1]的最长相等前后缀长度。
现在需要构造一个next数组，使得在P[i]匹配失败后通过next[i]获得P[0:i-1]的前缀长度。
static int * get_next(char const *p);
// return: first match index of s
int kmp_match(char const *s, char const *p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
int *next = _get_next(p);
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
}
free(next);
return p_ind == p_len ? s_ind : -1;
}
上面的kmp_match是通过bf_match改造的：s_ind不变，p_ind回溯。
但是存在一个bug，已知P[0]匹配失败时的前缀长度是0，按照 结论1 是P[0]去和S[j+1]匹配，匹配失败的代码是:
else
{
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
p_ind是0没有问题，但是s_ind没有更新，进入下一次循环还是P[0]和S[j]匹配，那么while是一直原地踏步。
应该增加一条P[0]匹配失败的条件分支，则：
if (s[s_ind] == p[p_ind])
{
// 匹配成功
s_ind++;
p_ind++;
}
else if (p_ind)
{
// 匹配失败，并且i=0时，更新j为j+1
s_ind++;
}
else
{
// 匹配失败，更新i，如果i=0，依旧更新为0
//=======================
// s_ind = s_ind - p_ind + 1;
p_ind = next[p_ind];
//=======================
}
为了简化代码，规定P[0]匹配失败时的前缀长度(next[0])为-1，则：
if (p_ind == -1 || s[s_ind] == p[p_ind])
{
// i=-1时，二次进入将i更新为0，j更新为j+1
s_ind++;
p_ind++;
}
else
{
// 匹配失败，更新i，如果i=0，更新为-1
p_ind = next[p_ind];
}
只看这段代码：只要进入循环时i == -1, 那么i = 0, j++。
Part 5
构造next数组有两种方式：1. 暴力构造；2.递推构造
原理：next[i]是P[i]匹配失败时P[0:i-1]的最长相等前后缀的长度。
暴力构造
static int _strcmp(
const char *p,
unsigned int len,
unsigned int index_1,
unsigned int index_2
)
{
int cnt = 0;
while (p[index_1] - p[index_2] == 0 && cnt < len) {
index_1++;
index_2++;
cnt++;
}
return cnt == len ? 1 : 0;
}
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
unsigned int next_ind = 1;
unsigned int substr_len;
unsigned int max_preffix_len;
for (; next_ind < p_len; next_ind++)
{
substr_len = next_ind;
max_preffix_len = sub_str_len - 1; // 从最长的前缀和后缀开始
while (max_preffix_len > 0)
{
if (_strcmp(p, max_preffix_len, 0
, substr_len - max_preffix_len))
{
break;
} else {
max_preffix_len--;
}
}
next[next_ind] = max_preffix_len;
}
return next;
}
递推构造
原理：根据前面构造好的最长前后缀长度推出这个前缀长度。
上图中，无论?处是多少，next[11]都应该是5，那??处该是多少。
P[11]最长相等前后缀的长度为5，如果P[11] == P[5]，如下图，那会出现P[0:5] == P[6:11] ，相当于将P[0:4] == P[6:10]等式两边都延长一个单位，等同于next[12] = next[11] + 1。
递推结论1：如果i > 1 && P[next[i-1]] == P[i-1], 那么next[i] = next[i-1] + 1。
如果P[11] != P[5]，那上面的情况是没戏了。那就找比最长短一点的，需要在最长前缀P[0:4]中找一个前缀，在最长后缀P[6:10]中找一个后缀。如下图。
因为P[0:4] == P[6:10]，所以就相当于在P[0:4]中找一对最长前后缀，如下图，前缀长度显然存放在next[5]中。
此时，如果P[11] == P[2]，那么next[12] = next[5] + 1。如下图。
如果P[11] != P[2]，像P[11] != P[2]一样。那就找更短一点的，需要在前缀P[0:1]中找一个前缀，在最长后缀P[9:10]中找一个后缀。
因为P[0:1] == P[9:10]，所以就相当于在P[0:1]中找一对最长前后缀，如下图，前缀长度显然存放在next[2]中。
此时，如果P[11] == P[0]，那么next[12] = next[2] + 1。如下图。
如果P[11] != P[0]，已经没有更短的前后缀了，next[12] = next[0] + 1 = -1 + 1 = 0。
递推结论2：如下图，为得到next[i]，需要P[i-1]的最长前后缀，如果P[i-1] == P[next[i-1]]，那么next[i] = next[i-1] + 1；如果不相等，找第二长的前后缀，如果P[i-1] == P[next[next[i-1]]], next[i] = next[next[i-1]] + 1; ...直到最后没有前后缀，P[i-1] == P[0], 则next[i] = 0 + 1, 这个0是在图中next[2]这样得来的，P[i-1] != P[0], 则next[i] = -1 + 1 = 0。
在过程中好像一直在找更短的前后缀，使得满足P[i-1] == P[前后缀长度]，致使P[i]得到最长的前后缀长度。实际只测试了条件，不满足就去找更短的前后缀长度来测试条件，前后缀长度之间的关系：next[当前前后缀长度] == 更短的前后缀长度。
代码实现：
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1; // P[0]的next[0]
int index = 1; // next数组当前索引，需要求next[index]
// k为next[index-1]，求next[index]时需要next[index-1]递推
int k = next[0];
while (index < p_len)
{
if (k == -1) // P[i-1]不等于P[0]，或i=1时，当前的前缀长度更新为0;
{
next[index] = k + 1;
index++;
k++;
// index++，原k=next[index-1]，更新为k=next[index]
}
// k=next[index-1]，匹配p[index - 1]和p[index-1的前缀长度]
else if (p[index - 1] == p[k])
{
next[index] = k + 1;
index++;
k++;
}
else
{
// 更新k为更短的前缀长度，在p[index-1] != p[k]且k=0时，会将k更新为-1
k = next[k] ;
}
}
return next;
}
// 合并前两个分支
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 1;
int k = -1;
while (index < p_len)
{
if (k == -1 || p[index - 1] == p[k])
{
next[index] = k + 1;
index++;
k++;
}
else
{
k = next[k] ;
}
}
return next;
}
// 优化index，从求next[index]变成求next[index+1]
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 0; // 从0开始
int k = -1;
while (index < p_len - 1)
{
if (k == -1 || p[index] == p[k])
{
index++;
k++;
next[index] = k;
}
else
{
k = next[k] ;
}
}
return next;
}
优化，连续失败情况：
上图中，在S[j]:?和P[11]处匹配失败，d != ?，下一步应该将P[5]和S[j]:? 匹配。观察得出P[5] == P[11]，那么P[5]和S[j]:?是一定匹配失败的。
也就是在P[i]处的匹配失败时，如果P[next[i]] == P[i]，那么P[next[i]]也一定是匹配失败的。这样说明构建的next数组是不合理的，所以在P[i] == P[next[i]]时，应该构建短一点的前后缀。如下图。
上图，将next[11]设置为2更合理。疑问：如果P[2]不是c，也是d怎么办？
上图中，无论是将next[11]设置为8、5、2都会匹配失败，应该设为0。但是这是反向递推，需要next回退几步；实际正向递推是这样：
得到next[2]=0，就得到next[5]，next[8]，next[11]。
优化后的方法：
static int * _get_next(char const *p)
{
int p_len = strlen(p);
int *next = malloc(sizeof(int) * p_len);
next[0] = -1;
int index = 0; // 从0开始
int k = -1;
while (index < p_len - 1)
{
if (k == -1 || p[index] == p[k])
{
index++;
k++;
// next[index] = k; 会出现p[next[index]] = p[index]连续失败的情况
if (p[index] != p[k])
{
next[index] = k;
}
else
{
// p[index] == p[k]时，回退一步k
next[index] = next[k];
}
}
else
{
k = next[k] ;
}
}
return next;
}
说明next出现非索引0处为-1的情况：
在上上面的kmp算法 结论1 中，next[i]=-1时，使i=0，j++；就是出现了P[0]处匹配失败。如下图：
图中，P[3]和P[6]都是前缀长度为0，匹配S[j]失败时，原本都是和P[0]再进行匹配，又因为P[3]和P[6]都等于P[0]，所以next[3]和next[6]都应该等于-1，使得进行P[0]和S[j+1]匹配。
在next数组构造中体现于：
if (p[index] != p[k])
{
next[index] = k;
}
else
{
// 在p[index] == p[0]时，next[index] = next[0] = -1
next[index] = next[k];
}
Sunday
Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。
在S串和P串存在匹配的字串s，必然有s == P，如果S串中包含P串没有的字符k，那么s中一定不包含k。Sunday算法就是基于这个事实。
上图中，P串中不包含字符S[5]，那么P与S匹配的情况可能是P1、P2、P3，绝不可能是P4。
Part 1
上图中，P串长度为7，与S串在P[4]处匹配失败，接下来P串要相对S串向后移一位。现在的问题是P串中是否包含S[7]？
上图中，P不包含字符S[7]，那么P串与S串处于上图中P1~7状态的对齐匹配都是会与S[7]匹配失败，只有在P8状态跳过与S[7]的匹配是有可能成功的。
结论1：P串长为length，P[0]与S[k]对齐进行匹配，在P串的任何匹配失败时，如果P串不包含字符S[k+length]，则P[0]与S[k+length+1]对齐匹配。
Part 2
如果P串中包含S[7]呢？如上图，P[1]、P[3]、P[5]都等于S[7]。
在上图中，S[7]与P[1]、P[3]、P[5]对齐时的P2、P4、P6状态都是有可能匹配成功的，而P1、P3、P5、P7对齐状态是绝不可能匹配成功的。
按照匹配顺序，P2状态是步幅最小的、合理的。
结论2：P串长为length，P[0]与S[k]对齐进行匹配，在P串的任何匹配失败时，如果P串包含字符S[k+length]，则S[k+length]与其在P串中最右出现的位置对齐，从P[0]匹配。
// return a hash table, key : byte, val : the byte in rightest
static int * _get_rightest(char const *p);
// return: first match index of s
int sunday_match(char const *s, char const *p)
{
int p_len = strlen(p);
int max_s_len = strlen(s) - p_len + 1;
int s_ind = 0;
int p_ind = 0;
int *rightest = _get_rightest(p);
while (s_ind < max_s_len && p_ind < p_len)
{
if (s[s_ind] == p[p_ind])
{
s_ind++;
p_ind++;
}
else
{
// 获取匹配失败时，类似上面S[7]位置的byte
int ac_index_s = s_ind + p_len - p_ind;
unsigned char ac = s[ac_index_s];
// ac字符在p串最右面的出现的位置
int ac_index_rp = rightest[ac];
if (index == -1)
{
// ac在p串中不存在，S串在ac字符的下一个字符开始比较
s_ind = ac_index_s + 1;
}
else
{
// 将ac与p[ac_index_rp]对齐
s_ind = ac_index_s - ac_index_rp;
}
p_ind = 0;
}
}
free(rightest);
return p_ind == p_len ? s_ind : -1;
}
Part 3
结论2需要一个统计P串中所有出现的字符和其在P串中最右边出现的位置。
c中的字符编码问题：linux64位c默认是使用utf-8编码，中英文占用字节不等长，没有高级api的加持很难统计，在匹配字符的情况下；如果，只是看作是字节匹配，那么无论什么编码都没关系，只要S串和P串的编码相同，并且在字节匹配最多有255种字节。linux64位下wchar_t是4个字节，按字符统计的效率更高，在utf-16编码的情况下字符大概有65535种，但是S串和P串可能需要向wchar_t转换。
// 无符号字符为index, 在p中出现的最右位置为值
static int * _get_rightest(char const *p)
{
int p_len = strlen(p);
int *char_on_rightest = mollac(sizeof(int) * 256);
int i;
for (i = 0; i < 256; i++)
{
char_on_rightest[i] = -1; // -1代表p中不存在等于i的字节
}
for (i = 0; i < p_len; i++)
{
char_on_rightest[p[i]] = i;
}
return char_on_rightest;
}
BM
1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。
Sunday算法是在BM算法的基础之后出现的，并且有相通的思想。
Part 1
BM算法的匹配顺序是从P[m-1]向P[0]方向匹配，P串从S串头向S串尾对齐。
Part 2
坏字符规则，这个思想和Sunday的思想是一致的，但是还没有Sunday算法完善。
上图中在P[3]:c处匹配失败，S[3]:a就叫坏字符。接下来P向后移，如果P[0]、P[1]、P[2]都不等于a，P[0]与P[4]对齐；多个等于a的，S[3]就和P位置小于3且靠右的a对齐。
上图中，P1[2]与S[3]对齐，这是理想的方式：实现时，如果S[j]和P[i]不匹配，那就要遍历P[0:i-1]寻找P[?]等于S[j]，或者记录P中所有字符在P串中的出现的所有的位置。按照这种理想实现的坏字符规则是在Horspool算法中，也只用这种规则。
实际上，只记录了P的中所有字符及其在P中最右出现的位置，和Sunday算法构造的字符位置hash数组是一样的。所以：
在BM算法中，坏字符规则会出现P相对S反向移动对齐。显然，这个规则是不足以支撑算法的，所以需要一个规则——好后缀规则。
BM算法的坏字符规则的最坏情况：
上图中，在S[1]和S[2]处循环连续失败。Sunday算法的坏字符在上图在P1情况下会选择S[6]为坏字符，在P2情况下选择S[5]为坏字符，所以P相对S的位移永远是正向的。
Part 3
好后缀规则，和坏字符规则思想是一致的。
上图中，在P[4]处匹配失败，P[5:6]和S[5:6]匹配，那么P[5:6]就是好后缀。接下来P相对S向后移动，如果在P[0:5]中存在"ab"，"ab"应该与S[5:6]对齐，存在多个"ab"取P[0:5]中最后一个；不存在P[0]与P[7]对齐。
P1在P[2:3]为"ab"，P2在P[0:5]中不包含"ab"。
另一种情况，如下图：
在P1[5]处匹配失败，P1[0:7]中不包含"abc"，但是存在P1前缀"bc"等于好后缀"abc"的子后缀"bc"，可以使P2[0:1]与S[7:8]对齐。
上图中，在P1[0:7]存在"abc"，P相对S最短位移，P[3:5]应与S[6:8]对齐。
结论：在P串存在与好后缀相同(但不是一个)的子串，子串与S串对齐；不存在与好后缀相同子串，如果存在与好后缀的子后缀相同的P串前缀，则前缀与S串对齐。
所以好后缀需要构造一个子串位置表和相同前后缀表。
Part 4
Bm算法有坏字符和好后缀两种规则，在P相对S移动时使用两种规则中移动距离更远的一个。
为什么是谁远使用谁？
接下来的不满足坏字符指P串中没有出现该坏字符，不满足好后缀指P串没有出现子串等于该后缀也没有前缀等于该后缀的子后缀。
不满足坏字符 && 不满足好后缀
匹配失败时，按坏字符规则对齐为P1，但P[6:8]是不满足好后缀规则的，P1的情况是注定匹配失败的。P2是按照好后缀规则对齐的，是可能匹配成功的。
这种情况谁远使用谁。
不满足坏字符 && 满足好后缀
情况1：子串等于好后缀，不是P前缀
P1是坏字符规则对齐，但是好后缀没有对齐，P1是注定匹配失败的；P2是好后缀规则对齐，但是P串中没有坏字符，P[0]永远不等于S[5]，P2是注定匹配失败的。两种情况都是失败的：
这种情况谁远使用谁。
情况2：子串等于好后缀，是P前缀
P1是坏字符规则对齐，并且P前缀等于好后缀；P2是好后缀规则对齐。两种情况都是成功的：
这种情况谁远使用谁。
情况3：前缀等于好后缀的子后缀
P1是坏字符规则对齐，但是好后缀没有对齐，失败；P2是好后缀规则对齐，可能会匹配成功。
这种情况谁远使用谁。
满足坏字符 && 不满足好后缀
情况1：坏字符只在P好后缀出现
P1串是坏字符规则对齐，相对S反向移动，失败；P2是不满足好后缀规则对齐，可能匹配成功。
这种情况谁远使用谁。
情况2：坏字符只在P匹配失败位置前出现
P1是满足坏字符的最大位移情况，但不满足好后缀规则注定失败；P2是不满足好后缀规则对齐，可能匹配成功。
这种情况谁远使用谁。
情况1附加：坏字符出现在好后缀和P匹配失败位置前
坏字符表只记录a在P[6]出现，没有记录P[2]处出现的a；P1和P2是情况1正常的移位；P3是假设P[2]:a和S[5]对齐的情况，如图，不满足好后缀规则，P3不能匹配成功。
满足坏字符 && 满足好后缀
情况1：位移相同
坏字符和好后缀在S串是连续的，在P串也是连续的，具有相同的位移。
这种情况谁远使用谁。
情况2：坏字符——间隔——好后缀
这种情况下，P1坏字符对齐则好后缀对不齐，P2好后缀对齐则坏字符对不齐。两种情况都会失败。
如果把P[1]:e替换成"abc"，那么P1就可能成功。如果把P[1]:a替换成"k"，那么就是情况1。
这种情况谁远使用谁。
情况3：好后缀——间隔——坏字符
P1坏字符对齐时，好后缀没有对齐，注定失败；P2是好后缀对齐，?处可能是等于坏字符的，P2是有可能匹配成功的。
这种情况谁远使用谁。
综上所述：在BM算法中，坏字符规则和好后缀规则量谁移动的距离远，就使用那个规则。在两种规则中好后缀规则是占主体的。
Part 5
构造BM算法需要一个坏字符表，一个好后缀表，一个相等前后缀表。
好后缀表以后缀长度为索引，以与其在P串最右的相等串的首索引为值。
相等前后缀表以后缀长度为索引，以0和1表示是否有前缀等于该后缀。
// return a hash table, key : byte, val : the index in rightest, -1 prefom no byte in p
static int * _get_bad_chars(char const *p);
// return a hash table, key : length of suffix, val : the index in rightest of substr equal suffix, -1 preform no substr equal suffix
static int * _get_good_suffixs(char const *p);
// return a hash table, key : length of suffix, val : 0 perform no prefix equal suffix, 1 perform a prefix equal suffix
static int * _get_prefix_equ_suffix(char const *p);
// return: first match index of s
int bm_match(char const *s, char const *p)
{
int p_len = strlen(p);
int s_len = strlen(s);
int p_ind = p_len - 1;
int s_ind = p_ind;
int *bc_ht = _get_bad_chars(p);
int *gs_ht = _get_good_suffixs(p);
int *pes_ht = _get_good_prefix_equ_suffix(p);
while (s_ind < s_len && p_ind > -1)
{
if (s[s_ind] == p[p_ind])
{
s_ind--;
p_ind--;
}
else
{
// 获取匹配失败时的坏字符在P最右的位置
int bc_ind = bc_ht[s[s_ind]];
// 坏字符对齐时，P相对S移动距离
int bc_re_ins;
if (bc_ind != -1)
{
bc_re_ins = p_ind - bc_ind;
}
else
{
bc_re_ins = p_ind + 1; // P[0]与P[p_ind+1]对齐
}
// 获取好后缀在P最右的位置
int gs_len = p_len - 1 - p_ind;
int gs_ind = gs_ht[gs_len];
// 好后缀对齐时，P相对S移动距离
int gs_re_ins;
if (gs_ind != -1)
{
gs_re_ins = p_ind + 1 - gs_ind;
}
else
{
// 没有好后缀，查找相等前后缀
int pes_len = gs_len - 1;
while (pes_len > 0)
{
if (pes_ht[pes_len]) {
break;
}
pes_len--;
}
if (pes_len > 0)
{
// 有相等的前后缀
gs_re_ins = p_len - pes_len; // P[0]与P[p_len - pes_len]对齐
}
else
{
// 没有相等的前后缀
gs_re_ins = p_len; // P[0]与P[p_len]对齐
}
}
// 坏字符与好后缀中最大的相对位移。
int max_re_ins = max(bc_re_ins, gs_re_ins);
// 找到现在与P[0]对齐的S[j]
int j = s_ind - p_ind;
s_ind = j + max_re_ins + p_len;
p_ind = p_len - 1;
}
}
free(bc_ht);
free(gs_ht);
free(pes_ht);
return p_ind ? -1 : s_ind;
}
优化点是：好后缀表为-1时，P相对S的位移一定是最大的，这时不需要坏字符。
Part 6
坏字符表
完全复制Sunday表
// return a hash table, key : byte, val : the index in rightest, -1 prefom no byte in p
static int * _get_bad_chars(char const *p)
{
int p_len = strlen(p);
int *bc = malloc(sizeof(int) * 256);
int i;
for (i = 0; i < 256; i++)
{
bc[i] = -1; // -1代表p中不存在等于i的字节
}
for (i = 0; i < p_len; i++)
{
bc[p[i]] == i;
}
return char_on_rightest;
}
好后缀表
// return a hash table, key : length of suffix, val : the index in rightest of substr equal suffix, -1 preform no substr equal suffix
static int * _get_good_suffixs(char const *p)
{
int p_len = strlen(p);
int *gs = malloc(sizeof(int) * p_len);
int i = 0;
for (; i < p_len; i++)
{
gs[i] = -1;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last, substr_len = 0;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
substr_len++
l_cur--;
r_cur--;
}
if (substr_len)
gs[substr_len] = i - substr_len + 1;
i++;
}
return gs;
}
// return a hash table, key : length of suffix, val : 0 perform no prefix equal suffix, 1 perform a prefix equal suffix
static int * _get_prefix_equ_suffix(char const *p)
{
int p_len = strlen(p);
int *pes = malloc(sizeof(int) * p_len);
int i = 0;
for (; i < p_len; i++)
{
pes[i] = 0;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
l_cur--;
r_cur--;
}
if (l_cur == -1)
pes[i+1] = 1;
i++;
}
}
合并3个表的方法
struct Bgp {
int *bc;
int *gs;
int *pes;
}
static struct Bgp * _get_all(const char *p)
{
int p_len = strlen(p);
struct Bgp *bgp = malloc(sizeof(struct Bgp));
int *bc= malloc(sizeof(int) * 256);
int *gs = malloc(sizeof(int) * p_len);
int *pes = malloc(sizeof(int) * p_len);
bgp->bc = bc;
bgp->gs = gs;
bgp->pes = pes;
int i;
for (i = 0; i < 256; i++)
bc[i] = -1;
for (i = 0; i < p_len; i++)
{
gs[i] = -1;
pes[i] = 0;
}
i = 0;
const int last = p_len -1;
while (i < last)
{
int l_cur = i, r_cur = last, substr_len = 0;
// 回溯
while (l_cur >= 0 && r_cur >= 0 && p[l_cur] == p[r_cur])
{
substr_len++
l_cur--;
r_cur--;
}
if (substr_len)
gs[substr_len] = i - substr_len + 1;
if (l_cur == -1)
pes[i+1] = 1;
bc[p[i]] = i;
i++;
}
bc[p[last]] = last;
return bgp;
}
总结
KMP、SUNDAY、BM字符串匹配算法。KMP只汲取P串自身的信息；SUNDAY算法汲取P和S的信息；BM汲取更多P和S的信息。
模式串长度为m，目标串长度为n。
则KMP的时间复杂度为O(m+n)，稳定。
SUNDAY和BM算法的搜索最优时间复杂度为O(n/m)，就是一匹配就失败并且坏字符不在模式串中，最差时间复杂度为O(m*n)，总是在模式串匹配到最后一位(BM是第一位)的失败，并且坏字符(BM还有好后缀)总是在比较后的位置。
SUNDAY的构造时间复杂度为O(m + 字符集大小)，BM算法的构造时间复杂度为O(m + 字符集大小 + m ^ 2)。字符集越大，BM和SUNDAY越优， 因为坏字符不在模式串的可能性越大。比如在只有0和1的两个字符的字符集，BM和SUNDAY和BF算法可能区别不大。模式串越短，坏字符不在模式串的可能性越大，构造时间越短。所以BM和SUNDAY算法在大字符集的情况下进行搜词的效率会高。
一般情况下，BM会比SUNDAY更优，因为BM是做坏字符加好后缀这一段字符的对齐，对齐机率比较低，模式串相对目标串移动快；而SUNDAY是做一个字符的对齐，对齐机率高，模式串相对目标串移动慢。
