sunday字元串匹配演算法

㈠ 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;
}

㈡ 編寫函數，該函數能在一個字元串中查找某個子串，並返回該子串首字出現的下標位置。

/*
Sunday-字元串匹配演算法--一種優於KMP的演算法
思想類似於BM演算法，只不過是從左向右匹配
遇到不匹配的看大串中匹配范圍之外的右側第一個字元在小串中的最右位置
另外：採用BM/KMP的預處理的做法，事先計算好移動步長，等到遇到不匹配的值直接使用
*/
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<time.h>
#include<string.h>
#include<windows.h>
usingnamespacestd;
//一個字元8位最大256種
#defineMAX_CHAR_SIZE256/*設定每個字元最右移動步長，保存每個字元的移動步長
如果大串中匹配字元的右側一個字元沒在子串中，大串移動步長=整個串的距離+1
如果大串中匹配范圍內的右側一個字元在子串中，大串移動距離=子串長度-這個字元在子串中的位置
*/
int*setCharStep(char*subStr)
{
int*charStep=newint[MAX_CHAR_SIZE];
intsubStrLen=strlen(subStr);
for(inti=0;i<MAX_CHAR_SIZE;i++)
charStep[i]=subStrLen+1;
//從左向右掃描一遍保存子串中每個字元所需移動步長
for(inti=0;i<subStrLen;i++)
{
charStep[(unsignedchar)subStr[i]]=subStrLen-i;
}
returncharStep;
}
/*
演算法核心思想，從左向右匹配，遇到不匹配的看大串中匹配范圍之外的右側第一個字元在小串中的最右位置
根據事先計算好的移動步長移動大串指針，直到匹配
*/
intsundaySearch(char*mainStr,char*subStr,int*charStep)
{
intmainStrLen=strlen(mainStr);
intsubStrLen=strlen(subStr);
intmain_i=0;
intsub_j=0;
while(main_i<mainStrLen)
{
//保存大串每次開始匹配的起始位置，便於移動指針
inttem=main_i;
while(sub_j<subStrLen)
{
if(mainStr[main_i]==subStr[sub_j])
{
main_i++;
sub_j++;
continue;
}
else{
//如果匹配范圍外已經找不到右側第一個字元，則匹配失敗
if(tem+subStrLen>mainStrLen)
return-1;
//否則移動步長重新匹配
charfirstRightChar=mainStr[tem+subStrLen];
main_i=tem+charStep[(unsignedchar)firstRightChar];
sub_j=0;
break;//退出本次失敗匹配重新一輪匹配
}
}
if(sub_j==subStrLen)
returnmain_i-subStrLen;
}
return-1;
}
intmain()
{
		unsigneStartTime=GetTickCount();
		unsigneEndTime;
		//隨機生成300位的二進制
		inti,j,t,k;
	charbins[1][300];//二維數組來存放
	srand((int)time(0));//種子，防止隨機數據不變
		for(i=0;i<1;i++){
		for(j=0;j<300;j++){
		bins[i][j]='0'+rand()%2;//放入隨機數
		}
		bins[i][j]=0;//字元串數組，所以最後一位''
		}
		char*mainStr=bins[0];
		printf("字元串
%s
",bins[0]);
char*subStr="010101";//需要查找的子字元串
printf("需要查找的字元串
010101
");
int*charStep=setCharStep(subStr);
cout<<"位置："<<sundaySearch(mainStr,subStr,charStep)<<endl;
uEndTime=GetTickCount();
printf("%umselapsed.
",uEndTime-uStartTime);
system("pause");
return0;
}

㈢ sunday 演算法的介紹

Sunday演算法是Daniel M.Sunday於1990年提出的字元串模式匹配。其核心思想是：在匹配過程中，模式串發現不匹配時，演算法能跳過盡可能多的字元以進行下一步的匹配，從而提高了匹配效率。

㈣ 【演算法筆記】字元串匹配

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演算法

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

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

㈥ 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;
}

㈦ 求C++字元串匹配的好方法，時間復雜度小於O（mn）

代碼基本都清空了……懶的寫……

一個叫Sunday匹配演算法 一個叫KMP匹配演算法 請自己網路吧........

㈧ 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

㈨ 編寫一個方法，輸出在一個字元串中，指定字元串輸出的次數

這樣寫目測應該可以 不過復雜度顯然是最高的 （n*m）

你應該去看看字元串匹配演算法 比如Sunday和Kmp（m+n）