字元串搜尋算法

字元串搜尋算法是一種搜尋算法，目的為在一長字元串中找出其是否包含某字元串。

基本介紹

• 中文名：字元串搜尋算法
• 類型：搜尋算法
• 直觀解釋：最直觀的解法是比對
• 如下例中：字元串haystack字元串needle

直觀解釋

，

char* haystack;

char* needle;

int hlen, nlen, found;int i,j,k;

found =0;

hlen =strlen(haystack);

nlen =strlen(needle);

for(i =0; i < hlen;++i)

{

for(j =0; j < nlen;++j)

{

if(haystack[i+j]!= needle[j])

break;

if(j == nlen -1)

found =1;

};

};

return found;

上例中，若字元串needle存在於字元串haystack中，則傳回1，否則傳回0。

但是此直觀算法的複雜度為 O(mn)，其中haystack的長度為n、needle的長度為m。