字符串查找算法

今天我来介绍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算法 的范例为了让读者更容易理解,并没有进行优化!

标签:计算机, 程序, 设计, 常用, 算法, 字符串, 查找

该文章由 Shiqi Qiu 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源:https://blog.fdawn.com/CPP/22.html

添加新评论