今天寫一篇文章，讨論如何判斷在一個字元數為N的字元串s1中是否存在一個字元數為k（k<N）的子字元串s2，并傳回第一次出現的位置，如果這篇文章對您有所幫助，不要吝啬對部落客點贊哦
1.首先最一般的算法就是将s1進行分割，将字串與s2進行比較，這種算法最壞情形下的時間複雜度為O（k*（N-k）），平均時間為k*（1+N-k）/2
2.對第一種算法稍微進行一些優化，我們首先在s1中查找s2的第一個字元，找到之後對後續字元進行比對，這樣使得平均情形有了較大改善
3.之後我應用了散列的想法，對這個問題重新進行考慮，假設s1字元串為A1A2……AN,s2字元串為P1P2……Pk,我們可以通過計算得到一個散列值Hp,并将該散列值與A1A2……Ak,A2A3……Ak+1，……進行比較，如果散列值比對，那我們再逐字元進行比較。
隻要hash函數設定恰當就可以實作如果AiAi+1……Ai+k-1已知那麼Ai+1Ai+2……Ai+k可以以常數的時間算出。這裡我寫的hash函數如下
unsigned int Hash(string s)
{
unsigned int hashval ;
int k = s.size();
for(auto p : s)
hashval = (hashval<<5)+p%32;
return hashval%(int)pow(32,k-1);
}
通過移位可以在常數時間内計算出相鄰子串的hash值，這種算法的最壞情形運作時間為O（k+N）加上反駁假比對所需的時間
4.對上述算法加以改進，可以将hash的碰撞次數降為0，這樣運作時間就為O（k+N）
unsigned int Hash(string s)
{
unsigned int hashval ;
int k = s.size();
for(auto p : s)
hashval = (hashval<<5)+p%32;
return hashval%(int)pow(32,k);
}
5.以上就是我利用已有知識所能想到的部分了，查閱相關論文後，了解到一個平均時間為O（N/k）的算法，下文将詳細介紹這種算法，文獻已标注在文章末尾。
為了友善表述，我們将s1稱為string，s2稱為pat
與第二種算法不同，這種算法通過pat中最右端的字元char來尋找子串，我們将與char對齊的string中字元的位置記為position,位置上的字元記為character
（1）如果character在pat中沒有出現，我們可以将position右移k個機關，而不是1個機關
（2）如果character在pat中出現但與position不比對，那我們從pat最右端尋找character第一次出現的位置，并通過移動使這兩個位置對齊
（3）如果char與position比對，那我們依次檢查char左邊緊挨的字元，重複前兩個步驟
但是，到這裡我們仍然存在改進的空間，在依次檢查字元時，遇到一對不比對的字元，這是我們将剛才已經檢查過的字元取出來作為子串，通過遞歸調用查詢出下一次該字元出現的位置，将這個偏移量與我們在（1）（2）中計算出的偏移量進行比較，取較大者作為position移動的值
以上叙述可能比較晦澀，下面以一個例子來進行說明（*為position）
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
‘F’未在pat中出現，是以右移7位
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
‘-’在pat中出現，移動使其對齊
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
‘T’比對，檢查下一位
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
‘L’不存在右移七位
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
繼續檢查
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
在右側找到“AT”使之對齊
pat: AT-THAT
string: ... WHICH-FINALLY-HALTS.--AT-THAT-POINT...
*
全部比對，檢查完畢
下面附上僞代碼
stringlen <---- length of string
i <---- patlen
top: if i > stringlen then return false
j<---- patlen
loop: if j=0 then return i+1
if string(i)=pat(j)
then
j<----j-1
i<----i-1
goto loop
close
i<----i+max(delta1(string(i)),delta2(j))
goto top
最後附上我自己的實作，供大家學習參考
/*
The expected value of the number of inspected characters in string is c*(i+patlen),where c<1 and gets smaller as patlen increases
*/
#include <string>
#include <iostream>
#include <math.h>
using namespace std;
int issubstr(int start,string pat,string str)
{
const int stringlen = str.size();
const int patlen = pat.size();
int i =start+patlen-1;
int j;
bool* inspect;
inspect = new bool[128];
for(auto k=0;k<i;k++)
inspect[pat[k]%128]=true;
int delta1,delta2;
string substr;
while(true){
if(i >stringlen-1) return -1;
j = patlen-1;
while(true)
{
if(j < 0) return i+1;
if(str[i]==pat[j])
{
j=j-1;
i=i-1;
}else break;
}
if(!inspect[str[i]%128])
delta1 = patlen;
else {
for(auto k=j-1;k>=0;k--)
if(pat[k]==str[i]){
delta1 = j-k;
break;
}
}
if(j!=patlen-1)
{
substr = pat.substr(j+1,patlen-j-1);
delta2= issubstr(i+2,substr,str)-i;
}else delta2=0;
if(delta2<0) return -1;
else i = i + max(delta1,delta2);
}
}
int main()
{
string str1,str2;
cout<<"Enter the str1: "<<endl;
cin>>str1;
cout<<"Enter the str2: "<<endl;
cin>>str2;
int n=issubstr(0,str1,str2);
if(n>0)
cout<<n;
else cout<<"Not Found!"<<endl;
}
> R.S.Boyer and J.S.Moore,"A Fast String Searching Algorithm",Communications of the ACM,20(1977),762-772
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)