Brute-Force算法的思想
1．BF(Brute-Force)算法
Brute-Force算法的基本思想是：
1) 從目標串s 的第一個字符起和模式串t的第一個字符進行比較，若相等，則繼續逐個比較后續字符，否則從串s 的第二個字符起再重新和串t進行比較。
2) 依此類推，直至串t 中的每個字符依次和串s的一個連續的字符序列相等，則稱模式匹配成功，此時串t的第一個字符在串s 中的位置就是t 在s中的位置，否則模式匹配不成功。
Brute-Force算法的實現
c語言實現：
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
#include <iostream>
using namespace std;
//宏定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSTRLEN 100
typedef char SString[MAXSTRLEN + 1];
/************************************************************************/
/*
返回子串T在主串S中第pos位置之后的位置，若不存在，返回0
*/
/************************************************************************/
int BFindex(SString S, SString T, int pos)
{
if (pos <1 || pos > S[0] ) exit(ERROR);
int i = pos, j =1;
while (i<= S[0] && j <= T[0])
{
if (S[i] == T[j])
{
++i; ++j;
} else {
i = i- j+ 2;
j = 1;
}
}
if(j > T[0]) return i - T[0];
return ERROR;
}
void main(){
SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};
SString T = {5,'a','b','c','a','c'};
int pos;
pos = BFindex( S, T, 1);
cout<<"Pos:"<<pos;
}
2．KMP算法
2.1 算法思想：
每當一趟匹配過程中出現字符比較不等時，不需要回溯I指針，而是利用已經的帶的“部分匹配”的結果將模式向右滑動盡可能遠的一段距離后，繼續進行比較。
即盡量利用已經部分匹配的結果信息，盡量讓i不要回溯，加快模式串的滑動速度。
需要討論兩個問題：
①如何由當前部分匹配結果確定模式向右滑動的新比較起點k？
② 模式應該向右滑多遠才是高效率的?
現在討論一般情況:
假設 主串：s: ‘s(1) s(2) s(3) ……s(n)’ ; 模式串 ：p: ‘p(1) p(2) p(3)…..p(m)’
現在我們假設 主串第i個字符與模式串的第j(j<=m)個字符‘失配’后，主串第i個字符與模式串的第k(k<j)個字符繼續比較。
此時，s(i)≠p(j)：
由此，我們得到關系式：即得到到1 到 j -1 的"部分匹配"結果:
‘P(1) P(2) P(3)…..P(j-1)’ = ’ S(i-j+1)……S(i-1)’
從而推導出k 到 j- 1位的“部分匹配”：即P的j-1～j-k＝S前i-1～i- (k -1))位
‘P(j – k + 1) …..P(j-1)’ = ’S(i-k+1)S(i-k+2)……S(i-1)’
由于s(i)≠p(j)，接下來s(i)將與p(k)繼續比較，則模式串中的前(k-1)個字符的子串必須滿足下列關系式，并且不可能存在 k’>k 滿足下列關系式：(k<j)
有關系式： 即(P的前k- 1 ~ 1位＝ S前i-1～i-(k-1) )位 ) ,：
‘P(1) P(2) P(3)…..P(k-1)’ = ’S(i-k+1)S(i-k+2)……S(i-1)’
現在我們把前面總結的關系綜合一下,有：
由上，我們得到關系：
‘p(1) p(2) p(3)…..p(k-1)’ = ‘p(j – k + 1) …..p(j-1)’
反之，若模式串中滿足該等式的兩個子串，則當匹配過程中，主串中的第i 個字符與模式中的第j個字符等時，僅需要將模式向右滑動至模式中的第k個字符和主串中的第i個字符對齊。此時，模式中頭k-1個字符的子串‘p(1) p(2) p(3)…..p(k-1)’ 必定與主串中的第i 個字符之前長度為k-1 的子串 ’s(j-k+1)s(j-k+2)……s(j-1)’相等，由此，匹配僅需要從模式中的第 k 個字符與主串中的第 i 個字符比較起 繼續進行。 若令 next[j] = k ,則next[j] 表明當模式中第j個字符與主串中相應字符“失配”時，在模式中需要重新和主串中該字符進行的比較的位置。由此可引出模式串的next函數：
根據模式串P的規律： ‘p(1) p(2) p(3)…..p(k-1)’ = ‘p(j – k + 1) …..p(j-1)’
由當前失配位置j(已知) ，可以歸納計算新起點k的表達式。
由此定義可推出下列模式串next函數值：
模式匹配過程:
KMP算法的實現:
第一步，先把模式T所有可能的失配點j所對應的next[j]計算出來；
第二步：執行定位函數Index_kmp（與BF算法模塊非常相似）
-
-
int KMPindex(SString S, SString T, int pos) { if (pos <1 || pos > S[0] ) exit(ERROR); int i = pos, j =1; while (i<= S[0] && j <= T[0]) { if (S[i] == T[j]) { ++i; ++j; } else { j = next[j+1]; } } if(j > T[0]) return i - T[0]; return ERROR; }
完整實現代碼：
// Test.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdio.h>
#include "stdlib.h"
#include <iostream>
using namespace std;
//宏定義
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSTRLEN 100
typedef char SString[MAXSTRLEN + 1];
void GetNext(SString T, int next[]);
int KMPindex(SString S, SString T, int pos);
/************************************************************************/
/*
返回子串T在主串S中第pos位置之后的位置，若不存在，返回0
*/
/************************************************************************/
int KMPindex(SString S, SString T, int pos)
{
if (pos <1 || pos > S[0] ) exit(ERROR);
int i = pos, j =1;
int next[MAXSTRLEN];
GetNext( T, next);
while (i<= S[0] && j <= T[0])
{
if (S[i] == T[j]) {
++i; ++j;
} else {
j = next[j];
}
}
if(j > T[0]) return i - T[0];
return ERROR;
}
/************************************************************************/
/* 求子串next[i]值的算法
*/
/************************************************************************/
void GetNext(SString T, int next[])
{ int j = 1, k = 0;
next[1] = 0;
while(j < T[0]){
if(k == 0 || T[j]==T[k]) {
++j; ++k; next[j] = k;
} else {
k = next[k];
}
}
}
void main(){
SString S = {13,'a','b','a','b','c','a','b','c','a','c','b','a','b'};
SString T = {5,'a','b','c','a','c'};
int pos;
pos = KMPindex( S, T, 1);
cout<<"Pos:"<<pos;
}
k值僅取決于模式串本身而與相匹配的主串無關。
我們使用遞推到方式求next函數：
1）由定義可知：
next[1] = 0;
2) 設 next[j] = k ,這個表面在模式串中存在下列關系：
‘P(1) ….. P(k-1)’ = ‘P(j – k + 1) ….. P(j-1)’
其中k為滿足1< k <j的某個值，并且不可能存在k` > 滿足:
‘P(1) ….. P(k`-1)’ = ‘P(j – k` + 1) ….. P(j-1)’
此時next[j+1] = ?可能有兩種情況：
（1） 若Pk = Pj，則表明在模式串中：
‘P(1) ….. P(k)’ = ‘P(j – k + 1) ….. P(j)’
并且不可能存在k` > 滿足： ‘P(1) ….. P(k`)’ = ‘P(j – k` + 1) ….. P(j)’
即next[j+1] = k + 1 推到=》：
next[j+1] = next[j] + 1;
(2) 若Pk
Pj 則表明在模式串中：
‘P(1) ….. P(k)’ ‘P(j – k + 1) ….. P(j)’
此時可把next函數值的問題看成是一個模式匹配的問題，整個模式串即是主串又是模式串，
而當前匹配的過程中，已有：
Pj-k+1 = P1， Pj-k+2 = P2，… Pj-1 = Pk-1.
則當PkPj時應將模式向右滑動至以模式中的第next[k]個字符和主串中的第 j 個字符相比較。
若next[k] = k`,且Pj= Pk`, 則說明在主串中的第j+1 個字符之前存在一個長度為k` (即next[k])的最長子串，和模式串
從首字符其長度為看k`的子串箱等。即
‘P(1) ….. P(k`)’ = ‘P(j – k` + 1) ….. P(j)’
也就是說next[j+1] = k` +1 即
next[j+1] = next[k] + 1
同理，若Pj Pk` ,則將模式繼續向右滑動直至將模式串中的第next[k`]個字符和Pj對齊，
… ,一次類推，直至Pj和模式中某個字符匹配成功或者不存在k`(1< k` < j)滿足，則:
next[j+1] =1;
-
/************************************************************************/ /* 求子串next[i]值的算法 */ /************************************************************************/ void GetNext(SString T, int next[]) { int j = 1, k = 0; next[1] = 0; while(j < T[0]){ if(k == 0 || T[j]==T[k]) { ++j; ++k; next[j] = k; } else { k = next[k]; } } }
next 函數值究竟是什么含義，前面說過一些，這里總結。設在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函數值next[n],1. next[n] = 0 表示S[m]和T[1]間接比較過了，不相等，下一次比較 S[m+1] 和T[1]2. next[n] =1 表示比較過程中產生了不相等，下一次比較 S[m] 和T[1]。3. next[n] = k >1 但k<n, 表示,S[m]的前k個字符與T中的開始k個字符已經間接比較相等了，下一次比較S[m]和T[k]相等嗎？4. 其他值，不可能。
注意：
（1）k值僅取決于模式串本身而與相匹配的主串無關。
（2）k值為模式串從頭向后及從j向前的兩部分的最大相同子串的長度。
（3）這里的兩部分子串可以有部分重疊的字符，但不可以全部重疊。
next[j]函數表征著模式P中最大相同前綴子串和后綴子串（真子串）的長度。
可見，模式中相似部分越多，則next[j]函數越大，它既表示模式T字符之間的相關度越高，也表示j位置以前與主串部分匹配的字符數越多。
即：next[j]越大，模式串向右滑動得越遠，與主串進行比較的次數越少，時間復雜度就越低（時間效率）。
轉自：http://blog.csdn.net/hguisu/article/details/7676786
原創文章，作者：s19930811，如若轉載，請注明出處：http://www.www58058.com/2800
