㈠ 【演算法筆記】字元串匹配
BF 演算法中的 BF 是 Brute Force 的縮寫，中文叫作暴力匹配演算法，也叫樸素匹配演算法：
主串和模式串：
在字元串 A 中查找字元串 B，那字元串 A 就是主串，字元串 B 就是模式串。我們把主串的長度記作 n，模式串的長度記作 m
我們在主串中，檢查起始位置分別是 0、1、2…n-m 且長度為 m 的 n-m+1 個子串，看有沒有跟模式串匹配的。
BF 演算法的時間復雜度是 O(n*m)
等價於
比如匹配Google 和Goo 是最好時間復雜度，匹配Google 和ble是匹配失敗的最好時間復雜度。
KMP演算法是一種改進的字元串匹配演算法，由D.E.Knuth與J.H.Morris和V.R.Pratt同時發現，因此人們稱它為克努特—莫里斯—普拉特演算法。KMP演算法主要分為兩個步驟：字元串的自我匹配，目標串和模式串之間的匹配。
看來網上很多的文章，感覺很多的都沒有說清楚，這里直接復制阮一峰的內容，講的很清晰
內容來自 http://www.ruanyifeng.com/blog/
首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜索詞"ABCDABD"的第一個字元，進行比較。因為B與A不匹配，所以搜索詞後移一位。
因為B與A不匹配，搜索詞再往後移。
就這樣，直到字元串有一個字元，與搜索詞的第一個字元相同為止。
接著比較字元串和搜索詞的下一個字元，還是相同。
直到字元串有一個字元，與搜索詞對應的字元不相同為止。
這時，最自然的反應是，將搜索詞整個後移一位，再從頭逐個比較。這樣做雖然可行，但是效率很差，因為你要把"搜索位置"移到已經比較過的位置，重比一遍。
一個基本事實是，當空格與D不匹配時，你其實知道前面六個字元是"ABCDAB"。KMP演算法的想法是，設法利用這個已知信息，不要把"搜索位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。
怎麼做到這一點呢？可以針對搜索詞，算出一張《部分匹配表》（Partial Match Table）。這張表是如何產生的，後面再介紹，這里只要會用就可以了。
已知空格與D不匹配時，前面六個字元"ABCDAB"是匹配的。查表可知，最後一個匹配字元B對應的"部分匹配值"為2，因此按照下面的公式算出向後移動的位數：
因為 6 - 2 等於4，所以將搜索詞向後移動4位。
因為空格與C不匹配，搜索詞還要繼續往後移。這時，已匹配的字元數為2（"AB"），對應的"部分匹配值"為0。所以，移動位數 = 2 - 0，結果為 2，於是將搜索詞向後移2位。
因為空格與A不匹配，繼續後移一位。
逐位比較，直到發現C與D不匹配。於是，移動位數 = 6 - 2，繼續將搜索詞向後移動4位。
逐位比較，直到搜索詞的最後一位，發現完全匹配，於是搜索完成。如果還要繼續搜索（即找出全部匹配），移動位數 = 7 - 0，再將搜索詞向後移動7位，這里就不再重復了。
下面介紹《部分匹配表》是如何產生的。
首先，要了解兩個概念："前綴"和"後綴"。 "前綴"指除了最後一個字元以外，一個字元串的全部頭部組合；"後綴"指除了第一個字元以外，一個字元串的全部尾部組合。
"部分匹配值"就是"前綴"和"後綴"的最長的共有元素的長度。以"ABCDABD"為例，
"部分匹配"的實質是，有時候，字元串頭部和尾部會有重復。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分匹配值"就是2（"AB"的長度）。搜索詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分匹配值），就可以來到第二個"AB"的位置。
BM（Boyer-Moore）演算法。它是一種非常高效的字元串匹配演算法，有實驗統計，它的性能是著名的KMP 演算法的 3 到 4 倍。
BM 演算法包含兩部分，分別是壞字元規則（bad character rule）和好後綴規則（good suffix shift）
未完待續
參考文章：
字元串匹配的Boyer-Moore演算法
㈡ 求出首次與字元串匹配的起始位置的代碼，要在c++里實現的。
1.樸素的模式匹配也叫B-F演算法int Find{int i,j;for(i=0;i<=curLength-pat.curLength;i++)//curlength是目標串的長度，pat.Length是模式串的長度{for(j=0;j<=pat.curlength;j++)//從ch[i] 開始的子串與模式串pat.ch進行比較if(ch[i+j]!=pat.ch[j])break;//ch是存放字元串的指針if(j==pat.curlength)return i;}return -1//找不到返回-1} 2. KMP演算法(最大特點是不回溯)int fastFind(int next[]){int posP=0;posT=0;//兩個串的掃描指針int lengthP=pat.curLength;int lengthT=curLength;while(posP<lengthP&&posT<lengthT)if(posP==-1||pat.ch[posP]==ch[posT]){posP++;posT++;}else posP=next[posP];if(posP<lengthP)return -1;//失敗else return posT-lengthP;} //計算next[j]的演算法void getNext(int next[]){int j=0,k=-1,lengthP=curLength;next[0]=-1;while(j<lengthP)if(k==-1||ch[j]==ch[k]){j++;k++;</p><p>next[j]=k;</p><p>}else k=next[k];}只是思路，不能直接上機實現，如果你能理解next[j]的原理，就很簡單了，希望對你有幫助。
㈢ 求 JAVA 字元串匹配 完美演算法
只需要實例化 類Matching 設置參數 並調用m.getIndex()方法就OK 請測試... public class Test18{
public static void main(String[] args){
Matching m = new Matching();
m.setOrgStr("ALSKLSHFKDLLS");
m.setSubStr("LS");
System.out.println(m.getIndex());
}
}
class Matching{
String orgStr ="";
String subStr ="";
public void setOrgStr(String orgStr){
this.orgStr = orgStr;
}
public void setSubStr(String subStr){
this.subStr = subStr;
}
public String getIndex(){
StringBuffer sb = new StringBuffer("{");
//根據關鍵字subStr來拆分字元串orgStr所得的字元串數組
String[] sub = orgStr.split(subStr);
int keyLength = subStr.length(); //關鍵字長度
int keySize = 0; //關鍵字個數
int subSize = sub.length; //子字元串個數
int subLength = 0; //子字元串長度
if(!orgStr.endsWith(subStr)){
keySize = subSize-1;
}else
keySize = subSize; int[] index = new int[keySize];//關鍵字下標數組
for(int i=0;i<keySize;i++){
subLength = sub[i].length();
if(i==0){
index[i]=subLength;
}else
index[i]=index[i-1]+subLength+keyLength;
}
if(keySize>0){
int l = keySize-1;
for(int i=0;i<l;i++){
sb.append(index[i]+",");
}
sb.append(index[l]);//最後一個關鍵字下標
}else{
sb.append("NULL");
}
sb.append("}");
return sb.toString();
}
}
㈣ c語言字元串匹配
1、c語言字元串匹配可以用strcmp函數。
2、strcmp是比較兩個字元串的大小,兩個字元串相同時返回0,第一個字元串大於第二個字元串時返回一個正值,否則返回負值.
比較兩個字元串的演算法是:逐個比較兩個串中對應的字元，字元大小按照ASCII碼值確定，從左向右比較，如果遇到不同字元，所遇第一對不同字元的大小關系就確定了兩個字元串的大小關系，如果未遇到不同字元而某個字元串首先結束，那麼這個字元串是較小的，否則兩個字元串相等。
㈤ 求字元串匹配BM演算法的代碼，要c或者c++的。
BM演算法的C語言實現：
// 函數：int* MakeSkip(char *, int)
// 目的：根據壞字元規則做預處理，建立一張壞字元表
// 參數：
// ptrn => 模式串P
// PLen => 模式串P長度
// 返回：
// int* - 壞字元表
int* MakeSkip(char *ptrn, int pLen)
{
int i;
//為建立壞字元表，申請256個int的空間
//PS:之所以要申請256個，是因為一個字元是8位，
// 所以字元可能有2的8次方即256種不同情況
int *skip = (int*)malloc(256*sizeof(int));
if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}
//初始化壞字元表，256個單元全部初始化為pLen
for(i = 0; i < 256; i++)
{
*(skip+i) = pLen;
}
//給表中需要賦值的單元賦值，不在模式串中出現的字元就不用再賦值了
while(pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--;
}
return skip;
}
// 函數：int* MakeShift(char *, int)
// 目的：根據好後綴規則做預處理，建立一張好後綴表
// 參數：
// ptrn => 模式串P
// PLen => 模式串P長度
// 返回：
// int* - 好後綴表
int* MakeShift(char* ptrn,int pLen)
{
//為好後綴表申請pLen個int的空間
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便給好後綴表進行賦值的指標
char *pptr = ptrn + pLen - 1;//記錄好後綴表邊界位置的指標
char c;
if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}
c = *(ptrn + pLen - 1);//保存模式串中最後一個字元，因為要反復用到它
*sptr = 1;//以最後一個字元為邊界時，確定移動1的距離
pptr--;//邊界移動到倒數第二個字元（這句是我自己加上去的，因為我總覺得不加上去會有BUG，大家試試「abcdd」的情況，即末尾兩位重復的情況）
while(sptr-- != shift)//該最外層循環完成給好後綴表中每一個單元進行賦值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;
//該do...while循環完成以當前pptr所指的字元為邊界時，要移動的距離
do{
while(p1 >= ptrn && *p1-- != c);//該空循環，尋找與最後一個字元c匹配的字元所指向的位置
p2 = ptrn + pLen - 2;
p3 = p1;
while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//該空循環，判斷在邊界內字元匹配到了什麼位置
}while(p3 >= ptrn && p2 >= pptr);
*sptr = shift + pLen - sptr + p2 - p3;//保存好後綴表中，以pptr所在字元為邊界時，要移動的位置
// PS:在這里我要聲明一句，*sptr = （shift + pLen - sptr） + p2 - p3;
// 大家看被我用括弧括起來的部分，如果只需要計算字元串移動的距離，那麼括弧中的那部分是不需要的。
// 因為在字元串自左向右做匹配的時候，指標是一直向左移的，這里*sptr保存的內容，實際是指標要移動
// 距離，而不是字元串移動的距離。我想SNORT是出於性能上的考慮，才這么做的。
pptr--;//邊界繼續向前移動
}
return shift;
}
// 函數：int* BMSearch(char *, int , char *, int, int *, int *)
// 目的：判斷文本串T中是否包含模式串P
// 參數：
// buf => 文本串T
// blen => 文本串T長度
// ptrn => 模式串P
// PLen => 模式串P長度
// skip => 壞字元表
// shift => 好後綴表
// 返回：
// int - 1表示成功（文本串包含模式串），0表示失敗（文本串不包含模式串）。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//計算字元串是否匹配到了盡頭
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//開始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
return 1;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根據壞字元規則計算跳躍的距離
shift_stride = shift[p_idx];//根據好後綴規則計算跳躍的距離
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}
㈥ 字元串匹配演算法是怎麼算的
這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ 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); } }
㈦ Java編程實現字元串的模式匹配
傳統的字元串模式匹配演算法（也就是BF演算法）就是對於主串和模式串雙雙自左向右，一個一個字元比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的演算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。
KMP 演算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt演算法，簡稱KMP演算法。KMP演算法是字元串模式匹配中的經典演算法。和BF演算法相比，KMP演算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得演算法時間復雜度只為O（n＋m）。
㈧ 如何用c++實現對txt文件的簡單字元串匹配演算法
char *subString(char *str,int star,int len) 這個原型聲明沒有問題，傳遞進去一個字元串，起始字元的位置，以及截取的長度。按照這個意思來寫最後是沒有問題的。返回值為字元型指針 可以在這個函數裡面聲明一個字元數組，最後將這個字元數組返回。
㈨ 字元串的模式匹配演算法
#include<iostream>
using namespace std;
void Next(char T[],int next[])
{ next[0]=-1;
int j=0,k=-1;
while(T[j]!='\0')
if((k==-1)||(T[j]==T[k]))
{ j++;
k++;
next[j]=k;
}
else k=next[k];
}
int KMP(char S[],char T[])
{ int i=0,j=0;
int next[10];
Next(T,next);
while((S[i]!='\0')&&(T[j]!='\0'))
{ if(S[i]==T[j]) {i++;j++;}
else j=next[j];
if(j==-1)
{ i++;j++; }
}
if(T[j]=='\0') return(i-j+1);
else return 0;
}
int main()
{ char a[100],b[100];
cout<<"please enter primary string :";
cin.getline(a,100);
cout<<"please enter substring:";
cin.getline(b,100);
if(KMP(a,b)==0)
cout<<"not exist!\n";
else cout<<"location is:"<<KMP(a,b)<<endl;
return 0;
}
具體的你自己看吧。
㈩ 字元串查找匹配--kmp演算法
KMP的關鍵是部分匹配表。理解KMP的主要障礙是沒有完全掌握部分匹配表中的值到底意味著什麼。試著用最簡單的話來解釋它們。
這是「abababca」模式的部分匹配表：
現在，為了談論其含義，我們需要了解正確的前綴和正確的後綴。
字元串中的所有字元，其中一個或多個字元被截斷。
「S」，「Sn」，「Sna」和「Snap」都是「Snape」的正確前綴。
截取的范圍是從字元串的第一個字元到倒數第二個字元。
字元串中的所有字元，一個或多個字元在開頭處截斷。
「agrid」，「grid」，「rid」，「id」和「d」都是「Hagrid」的正確後綴。
截取的范圍是從字元串的第二個字元到倒數第一個字元。
考慮到這一點，我現在可以給出部分匹配表中值的一句話含義：
現在來分析「abababca」這個模式串：
對「a」分析，只有一個字元串，沒有前綴和後綴，故值為0。
對「ab」分析，有一個正確的前綴（「a」）和一個正確的後綴（「b」），前綴和後綴不匹配，故值為0。
對「aba」分析，有兩個正確的前綴（「a」和「ab」）和兩個正確的後綴（「a」和「ba」）。正確的前綴「ab」與兩個正確的後綴中的任何一個都不匹配。但是，正確的前綴「a」與正確的後綴「a」匹配。因此，在這種情況下，匹配正確後綴的最長正確前綴的長度是1。
對四個字元（「abab」）分析，有三個正確的前綴（「a」，「ab」和「aba」）和三個正確的後綴（「b」，「ab」和「bab」）。「ab」在兩者中，並且是兩個字元長，因此值為2。
對「ababa」分析，有四個正確的前綴（「a」，「ab」，「aba」和「abab」）和四個正確的後綴（「a」，「ba」，「aba」和「baba」）。現在，有兩個匹配：「a」和「aba」都是正確的前綴和正確的後綴。由於「aba」比「a」長，所以它獲勝，因此值為3。
對「abababc」分析。即使沒有列舉所有正確的前綴和後綴，顯然也不會有任何匹配; 所有後綴都以字母「c」結尾，並且沒有前綴與之匹配，因此值為0。
對「abababca」分析，由於它們都以「a」開頭和結尾，我們知道它的值至少為1.但是，它就是它的結束點; 在長度為2或更高時，所有後綴都包含ac，而只有最長的前綴（「abababc」）包含「c」。這個七個字元的前綴與七個字元的後綴（「bababca」）不匹配，因此值為1。
當我們找到部分匹配時，我們可以使用部分匹配表中的值來跳過（而不是重做不必要的舊比較）。該公式的工作方式如下：
如果找到長度為partial_match_length的部分匹配table[partial_match_length] > 1，我們可以跳過前面的partial_match_length - table[partial_match_length - 1]字元。
假設我們將「abababca」模式與「bacbababaabcbab」相匹配。這里是我們的部分匹配表，以便於參考：
我們第一次獲得部分匹配是在這里：
這是partial_match_length為1. table[partial_match_length - 1]（或table[0]）的值為0，因此我們不會先跳過任何一個。我們得到的下一個部分匹配是：
這是partial_match_length為5. table[partial_match_length - 1]（或table[4]）的值為3.這意味著我們可以跳過前面partial_match_length - table[partial_match_length - 1]（或5 - table[4]或5 - 3或2）字元：
這是partial_match_length 3. table[partial_match_length - 1]（或table[2]）的值是1.這意味著我們可以跳過前面partial_match_length - table[partial_match_length - 1]（或3 - table[2]或3 - 1或2）字元：