字符串匹配算法
1、BF算法
Brute Force，也就是暴力算法。从左往右依次匹配主串和模式串，若不符合则模式串位置往后移动一位，该算法思路很清晰，写法最简单，但是时间效率很低。假设主串的长度是m，模式串的长度是n，在极端情况下，BF算法的最坏时间复杂度是O（mn）。
2、RK算法
Rabin-Karp，比较字符串的哈希值。每一个字符串都可以通过某种哈希算法，转换成一个整型数，这个整型数就是hashcode。相比于BF算法，PK算法采用哈希值比较的方式，免去了许多无畏的字符比较，若模式串和主串哈希值相等，则再一个字符一个字符比较，时间复杂度提升为是O（n），但是若哈希冲突比较多，则RK算法就退化成了BF算法。计算哈希值的常用方法有：
按位相加
这是最简单的方法，我们可以把a当做1，b当做2，c当做3......然后把字符串的所有字符相加，相加结果就是它的hashcode。
bce = 2 + 3 + 5 = 10
但是，这个算法虽然简单，却很可能产生hash冲突，比如bce、bec、cbe的hashcode是一样的。
int hashCode(string str){
int hashnum = 0;
for (int i = 0; i < str.length(); ++i) {
hashnum = hashnum + str[i] - 'a' + 1;
}
return hashnum;
}
int rabinKarp(string str, string pattern) {
int longStr = str.length();
int longPat = pattern.length();
int codeStr = hashCode(string(str.begin(), str.begin() + longPat));
int codePat = hashCode(pattern);
for (int i = 0; i < longStr - longPat + 1; ++i) {
string str1(str.begin() + i, str.begin() + i + longPat);
if (codePat == codeStr && str1 == pattern) {
return i;
}
if (i < longStr - longPat)
codeStr = codeStr - str[i] + str[i+ longPat];
}
return -1;
}转换成26进制数
既然字符串只包含26个小写字母，那么我们可以把每一个字符串当成一个26进制数来计算。
bce = 2(26^2) + 326 + 5 = 1435
这样做的好处是大幅减少了hash冲突，缺点是计算量较大，而且有可能出现超出整型范围的情况，需要对计算结果进行取模。
3、BM算法。
BM算法的检测顺序于其他算法相反，是从字符串的最右侧向最左侧检测。
坏字符规则
就是指模式串和子串当中不匹配的字符。
当模式串和主串的第一个等长子串比较时，子串的最后一个字符T就是坏字符：
不难发现，模式串的第1位字符也是T，这样一来我们就可以对模式串做一次“乾坤大挪移”，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较：
接下来，我们继续逐个字符比较，发现右侧的G、C、G都是一致的，但主串当中的字符A，是又一个坏字符。我们按照刚才的方式，找到模式串的第2位字符也是A，于是我们把模式串的字符A和主串中的坏字符对齐，进行下一轮比较：
接下来，我们继续逐个字符比较，这次发现全部字符都是匹配的，比较公正完成。如果坏字符在模式串中不存在，则直接把模式串挪到主串坏字符的下一位
坏字符代码：
int findCharacter(string pattern, char ch,int satrt) {
for (int i = satrt; i >= 0; --i)
if (pattern[i] == ch)
return i;
return -1;
}
int boyerMoore(string str, string pattern) {
int longStr = str.length();
int longPat = pattern.length();
int start = 0;
while (start <= longStr - longPat)
{
int i;
for (i = longPat - 1; i >= 0; --i) {
if (pattern[i] != str[i + start])
break;
}
if (i < 0)
return start;
int indexchar = findCharacter(pattern, str[i + start],i);
int offset = (indexchar != -1 ? i-indexchar:i+1);
start += offset;
}
return -1;
}好后缀规则
就是指模式串和子串当中相匹配的后缀。
若采用坏字符。从后向前比对字符，我们发现后面三个字符都是匹配的，到了第四个字符的时候，发现坏字符G，接下来我们在模式串找到了对应的字符G，但是按照坏字符规则，模式串仅仅能够向后挪动一位，这时候坏字符规则显然并没有起到作用。
我们回到第一轮的比较过程，发现主串和模式串都有共同的后缀“GCG”，这就是所谓的“好后缀”。如果模式串其他位置也包含与“GCG”相同的片段，那么我们就可以挪动模式串，让这个片段和好后缀对齐，进行下一轮的比较：
显然，在这个例子中，采用好后缀规则能够让模式串向后移动更多位，节省了更多无谓的比较。
如果模式串中不存在其他与好后缀相同的片段，需要进一步判断模式串的前缀是否和好后缀的后缀相匹配，免得挪过头。
总结：如何选择坏字符规则还是好后缀规则，需要计算两则的挪动距离，根据结果选择挪动距离长的，从而选取最优方案。
4、KMP算法。
和BM算法类似，KMP算法也在试图减少无谓的字符比较。为了实现这一点，KMP算法把专注点放在了已匹配的前缀。其空间复杂度为O(m)，时间复杂度为O(m+n);
第一轮，模式串和主串的第一个等长子串比较，发现前5个字符都是匹配的，第6个字符不匹配，是一个“坏字符”：
我们可以发现，在前缀“GTGTG”当中，后三个字符“GTG”和前三位字符“GTG”是相同的：
在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串。
第二轮，我们直接把模式串向后移动两位，让两个“GTG”对齐，继续从刚才主串的坏字符A开始进行比较：
显然，主串的字符A仍然是坏字符，这时候的匹配前缀缩短成了GTG：
第三轮，我们再次把模式串向后移动两位，让两个“G”对齐，继续从刚才主串的坏字符A开始进行比较：
以上就是KMP算法的整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。
next 数组
next数组到底是个什么鬼呢？这是一个一维整型数组，数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”。我们来看一下图：
当模式串的第一个字符就和主串不匹配时，并不存在已匹配前缀子串，更不存在最长可匹配前缀子串。这种情况对应的next数组下标是0，next[0]的元素值也是0。
如果已匹配前缀是G、GT、GTGTGC，并不存在最长可匹配前缀子串，所以对应的next数组元素值（next[1]，next[2]，next[6]）同样是0。
GTG的最长可匹配前缀是G，对应数组中的next[3]，元素值是1。
以此类推，
GTGT 对应 next[4]，元素值是2。
GTGTG 对应 next[5]，元素值是3。
有了next数组，我们就可以通过已匹配前缀的下一个位置（坏字符位置），快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。
比如下面的场景，我们通过坏字符下标5，可以找到next[5]=3，即最长可匹配前缀的下一个位置：
由于已匹配前缀数组在主串和模式串当中是相同的，所以我们仅仅依据模式串，就足以生成next数组。
最简单的方法是从最长的前缀子串开始，把每一种可能情况都做一次比较。
假设模式串的长度是m，生成next数组所需的最大总比较次数是1+2+3+4+......+m-2 次。
显然，这种方法的效率非常低，如何进行优化呢？
我们可以采用类似“动态规划”的方法。首先next[0]和next[1]的值肯定是0，因为这时候不存在前缀子串；从next[2]开始，next数组的每一个元素都可以由上一个元素推导而来。
已知next[i]的值，如何推导出next[i+1]呢？让我们来演示一下上述next数组的填充过程：
如图所示，我们设置两个变量i和j，其中i表示“已匹配前缀的下一个位置”，也就是待填充的数组下标，j表示“最长可匹配前缀子串的下一个位置”，也就是待填充的数组元素值。
当已匹配前缀不存在的时候，最长可匹配前缀子串当然也不存在，所以i=0，j=0，此时next[0] = 0。
接下来，我们让已匹配前缀子串的长度加1，此时的已匹配前缀是G，由于只有一个字符，同样不存在最长可匹配前缀子串，所以i=1，j=0，next[1] = 0。接下来，我们让已匹配前缀子串的长度继续加1：
此时的已匹配前缀是GT，我们需要开始做判断了：由于模式串当中 pattern[j] != pattern[i-1]，即G！=T，最长可匹配前缀子串仍然不存在。
所以当i=2时，j仍然是0，next[2] = 0。
接下来，我们让已匹配前缀子串的长度继续加1：
此时的已匹配前缀是GTG，由于模式串当中 pattern[j] = pattern[i-1]，即G=G，最长可匹配前缀子串出现了，是G。
所以当i=3时，j=1，next[3] = next[2]+1 = 1。
接下来，我们让已匹配前缀子串的长度继续加1：
此时的已匹配前缀是GTGT，由于模式串当中 pattern[j] = pattern[i-1]，即T=T，最长可匹配前缀子串又增加了一位，是GT。
所以当i=4时，j=2，next[4] = next[3]+1 = 2。
接下来，我们让已匹配前缀子串的长度继续加1：
此时的已匹配前缀是GTGTG，由于模式串当中 pattern[j] = pattern[i-1]，即G=G，最长可匹配前缀子串又增加了一位，是GTG。
所以当i=5时，j=3，next[5] = next[4]+1 = 3。
接下来，我们让已匹配前缀子串的长度继续加1：
此时的已匹配前缀是GTGTGC，这时候需要注意了，模式串当中 pattern[j] ！= pattern[i-1]，即T != C，这时候该怎么办呢？
这时候，我们已经无法从next[5]的值来推导出next[6]，而字符C的前面又有两段重复的子串“GTG”。那么，我们能不能把问题转化一下？
或许听起来有些绕：我们可以把计算“GTGTGC”最长可匹配前缀子串的问题，转化成计算“GTGC”最长可匹配前缀子串的问题。
这样的问题转化，也就相当于把变量j回溯到了next[j]，也就是j=1的局面（i值不变）：
回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即T！=C。那么我们可以把问题继续进行转化：
问题再次的转化，相当于再一次把变量j回溯到了next[j]，也就是j=0的局面：
回溯后，情况仍然是 pattern[j] ！= pattern[i-1]，即G！=C。j已经不能再次回溯了，所以我们得出结论：i=6时，j=0，next[6] = 0。
int* getNexts(string str) {
int* next = new int[str.length()]();
int j = 0;
for (int i = 2; i < str.length(); ++i) {
while (j != 0 && str[j] != str[i - 1])
j=next[j];
if (str[j] == str[i - 1])
j++;
next[i] = j;
}
return next;
}
int kmp(string str, string pattern) {
int* next = getNexts(pattern);
int index = 0;
for (int i = 0; i < str.length(); ++i) {
while (index > 0 && str[i] != pattern[index])
index = next[index];
if (str[i] == pattern[index])
++index;
if (index == pattern.length())
return i - pattern.length() + 1;
}
return -1;
} 
交通银行工作强度 39人发布
自愧不如