字元串搜尋算法

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

基本介紹

  • 中文名:字元串搜尋算法
  • 類型搜尋算法
  • 直觀解釋:最直觀的解法是比對
  • 如下例中:字元串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。

相關詞條

熱門詞條

聯絡我們