暴力字元串匹配演算法

❶ 字元串匹配演算法是怎麼算的

這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ boyermoore演算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 聲明： // 該段代碼只是BoyerMoore(名字也許不準確) 的基本思想，當 // 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。 // 該演算法的本質就是從字元串的右端而不是左端開始比較，這 // 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過 // strlen(sFind)個字元）， 如果最右邊的字元匹配則回溯。比如： // // pain // ^ 這是第一次比較n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 這是第二次比較，好爽呀！ // The rain in SpainThe rain in Spain // // 當然，這樣比較會產生一些問題，比如： // // pain // ^ （圖1） // The rain in SpainThe rain in Spain // // 如果比較到這兒，大家都會看到，只需再向後移到兩個字元 // 就匹配成功了，但如果接下去還按上面的方法跳strlen( sFind)的 // 話，就會錯過一次匹配！！！！！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子 // 串，說明有可能在不移動strlen(sFind) 的跨度就匹配成功，那就 // 人為地給它匹配成功的機會嘛！串一下pain串， 直接讓兩個a對齊 // 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可 // 以直接跨過strlen(sFind)個字元了！ 不知我說明白沒？ // // // 查詢串的長度 int nLenOfFind = lstrlen(sFind); // 被查詢串的長度 int nLenOfSrc = lstrlen(sSrc); // 指向查詢串最後一個字元的指針 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查詢串最後一個字元的指針 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比較過程中要用到的兩個指針 TCHAR * pSrc = sSrc; TCHAR * pFind; // 總不能一直讓它比較到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc <= pEndOfSrc ) { // 每次匹配都是從右向左，這是本演算法的核心。 pFind = pEndOfFind; // 如果比較不成功，被查詢串指針將向右串的字元數 int nMoveRightSrc; // 比較被查詢串的當前字元是否和查詢串的最右邊字 // 符匹配，如果匹配則回溯比較，如果全匹配了，該 // 干什麼，我就不用說了吧？:-) while ( pFind >= sFind ) { // TNND，白廢功夫比了！看看需要向右移動幾個 // 字元吧（如果說從右到左是本演算法的核心，則 // 判斷向右移幾個字元則是本演算法的技巧）。 if ( *pSrc != *pFind ) { // 被查詢串的當前字元是否在查詢串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 沒在，直接移lstrlen(sFind)個字元 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一個！接著向左回溯... pFind --; pSrc --; } // 如果在上面的while循環里每一次比較都匹配了 // 那就對了唄！告訴用戶找到了 if ( pFind < sFind ) return ( pSrc + 1 ); // 沒匹配成功，nMoveRightSrc上面已經算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序運行到這兒肯定是沒指望了！ return NULL; } 行了，函數寫完了，我們可以試一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("沒找到"); } //另外一個 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }

❷ BF的五種意思是什麼

1、BF，網路流行詞，即boyfriend的簡稱，就是男朋友的意思。該詞是相對於GF（girl friend）而言的。

2、BF，波束成形，是張韻聰博士在2004年IEEE期刊曾提出的一種編程演算法。

3、BF演算法，即暴力(Brute Force)演算法，是普通的模式匹配演算法，BF演算法的思想就是將目標串S的第一個字元與模式串T的第一個字元進行匹配，若相等，則繼續比較S的第二個字元和 T的第二個字元；若不相等，則比較S的第二個字元和T的第一個字元，依次比較下去，直到得出最後的匹配結果。

4、BF，是BUTFIRST的縮寫，目的是去掉第一個（在字元串、數字、數組）中。

5、BF：Brainfuck是一種極小化的計算機語言，它是由Urban Müller在1993年創建的。由於fuck在英語中是臟話，這種語言有時被稱為brainf*ck或brainf***，甚至被簡稱為BF。

❸ 給出字元串在KMP演算法中的Next數組

逐個查找對稱串。

只要循環遍歷這個子串，分別看前1個字元，前2個字元，3個... i個 最後到15個。

第1個a無對稱，所以對稱程度0

前兩個ag無對稱，所以也是0

依次類推前面0-4都一樣是0

最後一個是0～3都一樣是0

前綴next數組的求解演算法：

void SetPrefix(const char *Pattern, int prefix[])

{

int len=CharLen(Pattern);//模式字元串長度。

prefix[0]=0;

for(int i=1; i<len; i++)

{

int k=prefix[i-1];

//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推

while( Pattern[i] != Pattern[k] && k!=0 )

k=prefix[k-1]; //繼續遞歸

if( Pattern[i] == Pattern[k])//找到了這個子對稱，或者是直接繼承了前面的對稱性，這兩種都在前面的基礎上++

prefix[i]=k+1;

else

prefix[i]=0; //如果遍歷了所有子對稱都無效，說明這個新字元不具有對稱性，清0

}

}

(3)暴力字元串匹配演算法擴展閱讀：

設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b

模式串（下文中我們稱作W）為：a b a c a b

用暴力演算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。

而在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。

❹ kmp演算法的基本思想

主串：a b a c a a b a c a b a c a b a a b b，下文中我們稱作T
模式串：a b a c a b，下文中我們稱作W
在暴力字元串匹配過程中，我們會從T[0] 跟 W[0] 匹配，如果相等則匹配下一個字元，直到出現不相等的情況，此時我們會簡單的丟棄前面的匹配信息，然後從T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配的情況。這種簡單的丟棄前面的匹配信息，造成了極大的浪費和低下的匹配效率。
然而，在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
比如，在簡單的一次匹配失敗後，我們會想將模式串盡量的右移和主串進行匹配。右移的距離在KMP演算法中是如此計算的：在已經匹配的模式串子串中，找出最長的相同的前綴和後綴，然後移動使它們重疊。
在第一次匹配過程中
T: a b a c a a b a c a b a c a b a a b b
W: a b a c ab
在T[5]與W[5]出現了不匹配，而T[0]~T[4]是匹配的，現在T[0]~T[4]就是上文中說的已經匹配的模式串子串，現在移動找出最長的相同的前綴和後綴並使他們重疊：
T: a b a c aab a c a b a c a b a a b b
W: a b a c ab
然後在從上次匹配失敗的地方進行匹配，這樣就減少了匹配次數，增加了效率。
然而，有些同學可能會問了，每次都要計算最長的相同的前綴會不會反而浪費了時間，對於模式串來說，我們會提前計算出每個匹配失敗的位置應該移動的距離，花費的時間是常數時間。比如： j012345W[j]abacabF(j)001012當W[j]與T[i]不匹配的時候，設置j = F(j-1)
文獻中，朱洪對KMP演算法作了修改，他修改了KMP演算法中的next函數，即求next函數時不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]<>W[j]，他記修改後的next函數為newnext。顯然在模式串字元重復高的情況下，朱洪的KMP演算法比KMP演算法更加有效。
以下給出朱洪的改進KMP演算法和next函數和newnext函數的計算演算法。

❺ 字元串匹配演算法

boyermoore演算法的sample程序

TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind)
{
//
// 聲明：
// 該段代碼只是BoyerMoore(名字也許不準確)的基本思想，當
// 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。
// 該演算法的本質就是從字元串的右端而不是左端開始比較，這
// 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過
// strlen(sFind)個字元），如果最右邊的字元匹配則回溯。比如：
//
// pain
// ^ 這是第一次比較n和空格比
// The rain in SpainThe rain in Spain
//
// pain
// ^ 這是第二次比較，好爽呀！
// The rain in SpainThe rain in Spain
//
// 當然，這樣比較會產生一些問題，比如：
//
// pain
// ^ （圖1）
// The rain in SpainThe rain in Spain
//
// 如果比較到這兒，大家都會看到，只需再向後移到兩個字元
// 就匹配成功了，但如果接下去還按上面的方法跳strlen(sFind)的
// 話，就會錯過一次匹配！！！！！
//
// pain
// ^
// The rain in SpainThe rain in Spain
//
// 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子
// 串，說明有可能在不移動strlen(sFind)的跨度就匹配成功，那就
// 人為地給它匹配成功的機會嘛！串一下pain串，直接讓兩個a對齊
// 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可
// 以直接跨過strlen(sFind)個字元了！不知我說明白沒？
//
//

// 查詢串的長度
int nLenOfFind = lstrlen(sFind);
// 被查詢串的長度
int nLenOfSrc = lstrlen(sSrc);
// 指向查詢串最後一個字元的指針
TCHAR * pEndOfFind = sFind + nLenOfFind -1;
// 指向被查詢串最後一個字元的指針
TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1;

// 在比較過程中要用到的兩個指針
TCHAR * pSrc = sSrc;
TCHAR * pFind;

// 總不能一直讓它比較到win.com文件的地址去吧？嘻嘻！
while ( pSrc <= pEndOfSrc ) {

// 每次匹配都是從右向左，這是本演算法的核心。
pFind = pEndOfFind;

// 如果比較不成功，被查詢串指針將向右串的字元數
int nMoveRightSrc;

// 比較被查詢串的當前字元是否和查詢串的最右邊字
// 符匹配，如果匹配則回溯比較，如果全匹配了，該
// 干什麼，我就不用說了吧？:-)
while ( pFind >= sFind ) {

// TNND，白廢功夫比了！看看需要向右移動幾個
// 字元吧（如果說從右到左是本演算法的核心，則
// 判斷向右移幾個字元則是本演算法的技巧）。
if ( *pSrc != *pFind ) {

// 被查詢串的當前字元是否在查詢串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 沒在，直接移lstrlen(sFind)個字元
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;

break;
}

// 哈！又匹配成功了一個！接著向左回溯...
pFind --;
pSrc --;
}

// 如果在上面的while循環里每一次比較都匹配了
// 那就對了唄！告訴用戶找到了
if ( pFind < sFind )
return ( pSrc + 1 );

// 沒匹配成功，nMoveRightSrc上面已經算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}

// 程序運行到這兒肯定是沒指望了！
return NULL;
}

行了，函數寫完了，我們可以試一下了！

void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";

TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("沒找到");
}

//另外一個
void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}

void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];

/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}

❻ bf演算法是什麼

BF演算法，即暴力(Brute Force)演算法。

是普通的模式匹配演算法，BF演算法的思想就是將目標串S的第一個字元與模式串T的第一個字元進行匹配，若相等，則繼續比較S的第二個字元和 T的第二個字元；若不相等，則比較S的第二個字元和T的第一個字元，依次比較下去，直到得出最後的匹配結果。BF演算法是一種蠻力演算法。

如果一個多位數並且包含以上所有可能字元的密碼，其組合方法一定多的驚人，且每增加一位數，密碼組合數量會以數十倍指數成長，破譯的時間也會更長，有時可能長達數十年（即便考慮電腦性能依摩爾定律的進步），甚至更久。

由於窮舉法破解所消耗的時間不小於完成破解所需要的多項式時間，故從密碼學角度考慮，不認為窮舉法是有效的破解方法。

字典攻擊

破譯一個相當長度並且包含各種可能字元的密碼所耗費的時間相當長，其中一個解決辦法就是運用字典。所謂「字典攻擊」就是使用預先製作好的清單，例如：英文單字、生日的數字組合、以及各種常被使用的密碼，等等，利用一般人習慣設置過短或過於簡單的密碼進行破譯，很大程度上縮短了破譯時間。

防護手段

最重要的手段是在構建系統時要將系統設計目標定為即便受到暴力破解的攻擊也難以被攻破。以下列舉了一些常用的防護手段：

1、增加密碼的長度與復雜度。

2、在系統中限制密碼嘗試的次數。

3、密碼驗證時，將驗證結果不是立即返回而是延時若干秒後返回。

4、限制允許發起請求的客戶端的范圍。

5、禁止密碼輸入頻率過高的請求。

6、將密碼設置為類似安全令牌那樣每隔一定時間就發生變化的形式。

7、當同一來源的密碼輸入出錯次數超過一定閾值，立即通過郵件或簡訊等方式通知系統管理員。

8、人為監視系統，確認有無異常的密碼試錯。

9、使用雙因子認證，例如用戶登錄賬號密碼時，系統同時發送簡訊到用戶的手機，用戶需輸入簡訊內的認證碼。

❼ 字元串匹配演算法的基本思想是什麼

現在最常用的此類演算法是改進的KMP演算法。/*Name: KMP演算法演示Copyright: http://kapinter.spaces.msn.comAuthor: kapinterData: 08-07-06 20:17Description: 串的模式匹配的樸素演算法是O(N^2)的, 可以利用KMP(由D.E.Knuth, J.H.Morris, V.R.Pratt提出)演算法改進至線性的演算法. KMP演算法與樸素演算法的不同在於處理"失配"情況. 不同於將指針完全回溯, KMP演算法先根據已經部分匹配的信息, 將匹配的指針跳過不必匹配的位置.*/#include <iostream.h>#include <string.h>#include <iomanip.h>int Index(char *, char *);int KMP(char *, char *);int main(){char s[256] = "abcabaabcaccaaaabn";char *t[3] = {"abaabcac","aaaab","safasasf"};for (int i=0; i<3; i++) {cout<<"窮舉的模式匹配: "<<Index(s, t[i])<<endl;cout<<"KMP演算法: "<<KMP(s, t[i])<<endl;cout<<endl;}return 0;}int Index(char *s, char *t){int i = 0;int j = 0;int ls = strlen(s);int lt = strlen(t);while (i<ls && j<lt){if (s[i] == t[j]) {i++;j++;}else {i = i - j + 1;j = 0;}}if (j >= lt) {return (i - lt);}else {return -1;}}int KMP(char *s, char *t){void GetNext(char *, int, int *);int *next = new int[strlen(t)];int lt = strlen(t);int ls = strlen(s);int i, j;GetNext(t, lt, next);i = j = 0;while (i<ls && j<lt){if (j==-1 || s[i]==t[j]) {i++;j++;}else {j = next[j];}}if (j >= lt) {return (i - lt);}else {return -1;}}void GetNext(char *t, int lt, int *next){int i, j;if (lt > 0) { next[0] = -1; }j = -1;i = 0;while (i < lt){if (j==-1 || t[i]==t[j]) {i++;j++;if (t[i] == t[j]) {next[i] = next[j];}else {next[i] = j;}}else {j = next[j];}}cout<<"Next 數組: "<<endl;for (i=0; i<lt; i++) cout<<setw(4)<<t[i];cout<<endl;for (i=0; i<lt; i++) cout<<setw(4)<<next[i];cout<<endl;}/*窮舉的模式匹配: 3Next 數組:a b a a b c a c-1 0 -1 1 0 2 -1 1KMP演算法: 3窮舉的模式匹配: 12Next 數組:a a a a b-1 -1 -1 -1 3KMP演算法: 12窮舉的模式匹配: -1Next 數組:s a f a s a s f-1 0 0 0 -1 0 2 1KMP演算法: -1Press any key to continue

❽ 字元串匹配演算法，最快的是哪種

目前在我遇到的字元串匹配演算法中，最快的應該是sunday演算法了。。
(BF、KMP、BM、sunday)

❾ 最容易理解，容易學的的字元串匹配演算法

最簡單的是暴力匹配 叫什麼我忘了 就是雙重for循環 復雜度是n1*n2

其次是Sunday演算法 具體過程自己搜吧 也不難 算是劍走偏鋒的 而且它的速度一般是最快的 復雜度 n1+n2

然後是kmp演算法 純論速度它還不如Sunday 演算法 而且也比較難理解 但是它對於後面的一些其他的學習是有必要的 復雜度 n1+n2