字符串模式匹配（BF算法和KMP算法）

本文主要是介绍字符串模式匹配（BF算法和KMP算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

字符串模式匹配：

在主串s中寻找子串t，若主串第i个下标开始的字符串同子串t完全相同，则返回下标i，若遍历完主串s未找到匹配，则返回-1。

BF（Brute Force)算法：

BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果，BF算法在每次字符不匹配时， 都要回溯到开始位置，时间开销较大，复杂度为O(length(s)*length(t))

KMP算法：

KMP算法解决了这个缺点，简单的说，KMP算法就是研究当字符串不匹配时，T应当回溯到什么位置，以避免多余的回溯和比较过程。利用已经部分匹配这个有效信息，保持主串S指针不回溯，通过修改子串T指针，让模式串尽量地移动到有效的位置。
因为在T的每一个位置都可能发生不匹配，因此通常使用一个int型的数组next来标志当T中的每个元素不匹配时，子串T指针应该回溯的位置。

关于next数组的推导问题，可以参考这篇文章。

这里给出两种算法的实现程序：

#include "stdafx.h"
#include <iostream>
using namespace std;
namespace StringPattern
{//BF 算法的实现int stringPattern_BF(const char* s,int sLen, const char* t,int tLen){int i = 0, j = 0;while (i < sLen&&j<tLen){if (s[i] == t[j]){i++;j++;}else{i = i - j + 1;	//不匹配，主串下标前进一个位置j = 0;}}if (j == tLen)	return i-j;else return -1;}void getNext(const char* t,int *next){int j = 0,k=-1;next[0] = -1;int len = strlen(t);while (j < len-1){if ((k ==-1) || t[j] == t[k]){if (t[++j] == t[++k])	//当两个字符相等时后面的不匹配前面的当然不匹配，直接按照前面字符不匹配时处理next[j] = next[k];elsenext[j] = k;}elsek = next[k];}}int stringPattern_KMP(const char* s,int sLen, const char* t,int tLen){int *next = new int[tLen];getNext(t, next);int i=0, j=0;while (i < sLen&&j < tLen){if (j == -1 || s[i] == t[j]){i++;j++;}else{j = next[j];}}if (j == tLen)return i - j;else return -1;}void test(){char* s = "woaibeijingtiananmen";char* t = "ijing";cout << stringPattern_BF(s,strlen(s),t,strlen(t)) << endl;cout << stringPattern_KMP(s, strlen(s), t, strlen(t)) << endl;}
}int _tmain(int argc, _TCHAR* argv[])
{StringPattern::test();return 0;
}

运行结果：

这篇关于字符串模式匹配（BF算法和KMP算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---