字符串查找算法
今天我来介绍2个比较常用的字符串查找算法，它们分别是BF算法(Brute Force)和KMP算法。虽然这两个算法都不是效率最高的，但是它们却是最基础的和改进的。
BF算法是最普通的字符串查找算法，这个算法虽然编写效率高，但是执行效率超低。因为BF算法的思想是用模式串（需要查找的字符串）的第一个字符匹配目标串（被查找的字符串）的第一个字符，如果相同则将模式串的第二个字符匹配目标串的第二个字符。如果第一个字符不相同，就将模式串于目标串后移一位，拿目标串的第二个字符与模式串的第一个字符比较，如此类推。这样的思想是不好的，因为会做很多愚蠢的无用功动作，下面的KMP算法就能很好地改善这样的行为。
KMP算法 是从 BF算法 改进过来的，它把匹配失败的信息记录下来，并且做成一个可以减少匹配次数的数组。这个数组叫做“Next数组”，这样的做法是为了改良 BF算法 的硬伤：模式串的第一个字符与目标串不相同则将模式串后移一位，这样会丢弃掉前面所有匹配失败的信息。所以就用 Next数组 把匹配失败的信息都记录下来。如果在哪失配了，就通过 Next数组 的指向并进行下一轮的匹配。
Next数组 的主要实现原理：
[如何正确地阅读以下内容]
请先从上到下阅读绿色的分隔线左边的内容，然后再通过分隔线右边的内容与分隔线左边的图片进行阅读。蓝色的圆框标注的是顺序步骤。
BF算法与KMP算法的实现代码：
#include <iostream>
using namespace std;
void KMP(char *String, char *Key);
void KMPGetNext(char *String, int *&Next);
void BF(char *String, char *Key);
int main(){
char *String = "ababcf0g";
char *Key = "abc";
BF(String, Key);
KMP(String, Key);
system("pause");
return 0;
}
void BF(char *String, char *Key){
int i, j, SLen = strlen(String), KLen = strlen(Key);
i = j = 0;
while(i < SLen && j < KLen){
if(String[i] == Key[j]){
i++;
j++;
}else{
i = i - j + 1;
j = 0;
}
}
if(j == KLen){
cout << i - KLen << endl;
}else{
cout << -1 << endl;
}
}
void KMP(char *String, char *Key){
int i = 0, j = 0, SLen = strlen(String), KLen = strlen(Key), *Next = new int[SLen]();
KMPGetNext(String, Next); //获取Next数组
while(i < SLen && j < KLen){
if(j == -1 || String[i] == Key[j]){
i++;
j++;
}else{
j = Next[j]; //回溯
}
}
if(j == KLen){
cout << i - KLen << endl;
}else{
cout << -1 << endl;
}
}
void KMPGetNext(char *String, int *&Next){
int i = -1, j = 0, SLen = strlen(String);
Next[0] = -1;
while(j < SLen){
if(i == -1 || String[i] == String[j]){
i++;
j++;
*(Next + j) = i; //在Next数组 后缀+1 的位置放入 前缀+1 的值
}else{
i = *(Next + i); //回溯
}
}
}
[温馨提示]
我写的这个 KMP算法 的范例为了让读者更容易理解，并没有进行优化！