類似的efficent版本的strstr

Question

這裏是一個普遍實現

int stridx (char[] src, char[] str){ 
    int i,j,k; 
    for(i=0;i < (src.len - str.len);i++){ 
     for(j=i,k=0; str[k] != '\0' && str[k] == src[i]; j++,k++); 
     if(k> 0 && str[k]=='\0') return i; 
    } 
    return -1; 
} 

算法的最壞情況可能是n^2，如果我們有aaaaaaaaaaaaaaaaaaaaaaaa（假設src和STR很長，長度他們非常接近）。

我可以有更好的算法嗎？

Answer 1

你可以使用Boyer-Moore算法，它是O（n）。 Here's示例C代碼。

Answer 2

這不是必要計算串的長度：

char *strr(char *s1,char *s2) 
    { 
    int i,j; 
    for(i=0;s1[i];i++) 
     if(s1[i]==s2[0]) 
      for(j=0;s1[i+j]==s2[j];j++) 
       if(!s2[j+1]) return &s1[i]; 
    return NULL; 
    } 

Answer 3

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm是另一線性時間算法。 OTOH，簡單的算法仍然存在，因爲在實踐中，他們對於大多數人實際搜索的字符串更快。