A. 字元串匹配演算法是怎麼算的
這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ 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); } }
B. KMP匹配演算法
不懂得話，就自己跟上三四遍就好了，代碼附上
有什麼不懂的就問，不過還是盡量自己鑽研的好
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
const int maxLen = 128;
class String
{
int curLen; //串的當前長度
char *ch; //串的存儲數組
public:
String (const String & ob);
String (const char *init);
String ();
~String ()
{
delete [] ch;
}
int Length () const
{
return curLen;
}
String *operator () ( int pos, int len );
int operator == ( const String &ob )const
{
return strcmp (ch, ob.ch) == 0;
}
int operator != ( const String &ob ) const
{
return strcmp (ch, ob.ch) != 0;
}
int operator !() const
{
return curLen == 0;
}
String &operator = (const String &ob);
String &operator += (const String &ob);
char &operator [] (int i);
int fastFind ( String pat ) const;
//void fail (const char *T,int* &f);
void fail (int* &f);
};
String::String ( const String &ob ) //復制構造函數：從已有串ob復制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = ob.curLen;
strcpy ( ch, ob.ch );
}
String::String ( const char *init ) //復制構造函數: 從已有字元數組*init復制
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = strlen (init);
strcpy ( ch, init );
}
String::String ( )//構造函數：創建一個空串
{
ch = new char[maxLen+1];
if ( !ch )
{
cout << "Allocation Error\n";
exit(1);
}
curLen = 0;
ch[0] = '\0';
}
String *String::operator ( ) ( int pos, int len )//從串中第pos個位置起連續提取len個字元//形成子串返回
{
String *temp = new String;
if ( pos < 0 || pos+len -1 >= maxLen|| len < 0 ) //返回空串
{
temp->curLen = 0;
temp->ch[0] = '\0';
}
else //提取子串
{
//動態分配
if ( pos+len -1 >= curLen )
len = curLen - pos;
temp->curLen = len; //子串長度
for ( int i=0, j=pos; i<len; i++, j++ )
temp->ch[i] = ch[j]; //傳送串數組
temp->ch[len] = '\0'; //子串結束
}
return temp;
}
String &String::operator = ( const String &ob )//串賦值：從已有串ob復制
{
if ( &ob != this )
{
delete [ ] ch;
ch = new char [maxLen+1]; //重新分配
if ( ! ch )
{
cerr << "out of memory!\n ";
exit (1);
}
curLen = ob.curLen; //串復制
strcpy ( ch, ob.ch );
}
else
cout << "Attempted assignment of a String to itself!\n";
return *this;
}
char &String::operator [] ( int i ) //按串名提取串中第i個字元
{
if ( i < 0 && i >= curLen )
{
cout << "Out Of Boundary!\n ";
exit (1) ;
}
return ch[i];
}
String &String::operator += ( const String &ob )
{ //串連接
char * temp =ch; //暫存原串數組
curLen += ob.curLen; //串長度累加
ch = new char [maxLen+1];
if ( ! ch )
{
cerr << "Out Of Memory!\n ";
exit (1) ;
}
strcpy ( ch, temp ); //拷貝原串數組
strcat ( ch, ob.ch ); //連接ob串數組
delete [ ] temp;
return *this;
}
int String :: fastFind ( String pat ) const //帶失效函數的KMP匹配演算法
{
int posP = 0, posT = 0;
int lengthP = pat.curLen, lengthT = curLen;
int *f=new int[lengthP];
memset(f,-1,lengthP);
pat.fail (f);
while ( posP < lengthP && posT < lengthT )
{
if ( pat.ch[posP] == ch[posT] )
{
posP++;
posT++; //相等繼續比較
}
else if ( posP == 0 )
{
posT++;
}//不相等
else
{
posP = f[posP-1]+1;
}
}
delete []f;
if ( posP < lengthP )
return -1;
else
return posT - lengthP;
}
void String::fail (int* &f)//計算失效函數
{
int lengthP = curLen;
f[0] = -1; //直接賦值
for ( int j=1; j<lengthP; j++ ) //依次求f [j]
{
int i = f[j-1];
if ( *(ch+j) != *(ch+i+1) && i >= 0 )
i = f [i]; //遞推
if ( *(ch+j) == *(ch+i+1) )
f [j] = i+1;
else
f [j] = -1;
}
}
/**/
void main()
{
int end;
cout<<"hello!\n";
String s1("acabaabaabcacaabc");
String s2=("abaabcac");
end=s1.fastFind(s2);
cout<<end<<endl;
}
C. sunday演算法解析
例如我們要在"substring searching algorithm"查找"search"，剛開始時，把子
串與文本左邊對齊，
substring searching algorithm
search
^
結果在第二個字元處發現不匹配，於是要把子串往後移動。但是該移動多少呢？這
就是各種演算法各顯神通的地方了，最簡單的做法是移動一個字元位置；KMP是利用
已經匹配部分的信息來移動；BM演算法是做反向比較，並根據已經匹配的部分來確定
移動量。這里要介紹的方法是看緊跟在當前子串之後的那個字元（上圖中的'i'。
顯然，不管移動多少，這個字元是肯定要參加下一步的比較的，也就是說，如果下
一步匹配到了，這個字元必須在子串內。所以，可以移動子串，使子串中的最右邊
的這個字元與它對齊。現在子串'search'中並不存在'i'，則說明可以直接跳過一
大片，從'i'之後的那個字元開始作下一步的比較，如下圖：
substring searching algorithm
search
^
比較的結果，第一個字元就不匹配，再看子串後面的那個字元，是'r',它在子串中
出現在倒數第三位，於是把子串向前移動三位，使兩個'r'對齊，如下：
substring searching algorithm
search
D. 字元串匹配演算法的基本思想是什麼
現在最常用的此類演算法是改進的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
E. 字元串匹配演算法，最快的是哪種
目前在我遇到的字元串匹配演算法中，最快的應該是sunday演算法了。。
(BF、KMP、BM、sunday)
F. C++ 字元串最後出現的位置和取字元串左邊的指定幾個字元
/*
''在s[]中最後出現的位置是:11
t[] = 123
Press any key to continue
*/
#include<stdio.h>
#include<string.h>
//返回ch在s[]最後出現的位置。返回0表示在s[]中沒有發現字元ch
intLastPos(chars[],charch){
inti,pos=0;//
for(i=0;s[i];++i)
if(s[i]==ch)pos=i+1;
returnpos;
}
//復制s[]中右邊的n個字元到t[]中
char*RightStr(chars[],chart[],intn){
inti,j,len=strlen(s);
t[0]=' ';
if(n>=len)strcpy(t,s);
elseif(n>0&&n<len){
i=len-n;
j=0;
while(t[j++]=s[i++])
;
}
returnt;
}
intmain(){
chars[]="C:\WINDOWS\123";
chart[20];
printf("'\'在s[]中最後出現的位置是:%d ",LastPos(s,'\'));
printf("t[]=%s ",RightStr(s,t,3));
return0;
}
G. 求C++字元串匹配的好方法，時間復雜度小於O（mn）
代碼基本都清空了……懶的寫……
一個叫Sunday匹配演算法 一個叫KMP匹配演算法 請自己網路吧........
H. 關於一個字元串匹配演算法
我看了一下代碼的，大概覺得它主要實現的功能是查找*y對應字元串中是否有與*x對應的字元串相等的子字元串存在，如果存在則返回該子串第一個字元在*y中的位置。
但是你沒有把問題說清楚，比如preBmBc和memcmp這兩個函數是在你給的程序中沒有定義的，我猜了好久都不能猜出他們確切的用途。我估計你們老師主要也是叫你們實現這兩個函數吧。。
如果你能在把問題給得詳細的。。我可以繼續幫你想想。。
不愧是畢業設計的題目啊，確實有點難度啊。我覺得那個函數不是一個簡單的字元串匹配演算法，它是一個多重字元串匹配演算法。我給你個C語言的例子你參考一下吧。一下兩下我也搞不出來了，真不好意思。
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);
}
}