字元串模式比對（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];
				else
					next[j] = k;
			}
			else
				k = 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;
}
           

運作結果：