ここ

Question

をSTRSTRに似efficentバージョンは一般的な実装

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

である我々はaaaaaaaaaaaaaaaaaaaaaaaa（SRCとstrの両方が非常に長いと仮定すると、長さを持っている場合は、アルゴリズムの最悪のケースでは、^ 2のnかもしれませんそれらの非常に近いです）。

もっと良いアルゴリズムはありますか？

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では、単純なアルゴリズムは、実際には人々が実際に検索する文字列のほうが高速であるためにとどまります。