的strstr（）的字符串，它是不是空終止

Question

我該怎麼做了就地相當於strstr()的用C計串（即不空值終止）？

Answer 1

如果你害怕O（m * n個）的行爲 - 基本上，你不用，這樣的情況不會自然發生 - 這裏有一個KMP實現我已經躺在附近我已經修改採取乾草堆的長度。也是一個包裝。如果您想重複搜索，請自行編寫並重新使用borders陣列。

沒有缺陷保證，但它似乎仍然有效。

int *kmp_borders(char *needle, size_t nlen){ 
    if (!needle) return NULL; 
    int i, j, *borders = malloc((nlen+1)*sizeof(*borders)); 
    if (!borders) return NULL; 
    i = 0; 
    j = -1; 
    borders[i] = j; 
    while((size_t)i < nlen){ 
     while(j >= 0 && needle[i] != needle[j]){ 
      j = borders[j]; 
     } 
     ++i; 
     ++j; 
     borders[i] = j; 
    } 
    return borders; 
} 

char *kmp_search(char *haystack, size_t haylen, char *needle, size_t nlen, int *borders){ 
    size_t max_index = haylen-nlen, i = 0, j = 0; 
    while(i <= max_index){ 
     while(j < nlen && *haystack && needle[j] == *haystack){ 
      ++j; 
      ++haystack; 
     } 
     if (j == nlen){ 
      return haystack-nlen; 
     } 
     if (!(*haystack)){ 
      return NULL; 
     } 
     if (j == 0){ 
      ++haystack; 
      ++i; 
     } else { 
      do{ 
       i += j - (size_t)borders[j]; 
       j = borders[j]; 
      }while(j > 0 && needle[j] != *haystack); 
     } 
    } 
    return NULL; 
} 

char *sstrnstr(char *haystack, char *needle, size_t haylen){ 
    if (!haystack || !needle){ 
     return NULL; 
    } 
    size_t nlen = strlen(needle); 
    if (haylen < nlen){ 
     return NULL; 
    } 
    int *borders = kmp_borders(needle, nlen); 
    if (!borders){ 
     return NULL; 
    } 
    char *match = kmp_search(haystack, haylen, needle, nlen, borders); 
    free(borders); 
    return match; 
} 

Answer 2

看看下面的功能是否適合你。我沒有徹底測試過，所以我建議你這樣做。

char *sstrstr(char *haystack, char *needle, size_t length) 
{ 
    size_t needle_length = strlen(needle); 
    size_t i; 

    for (i = 0; i < length; i++) 
    { 
     if (i + needle_length > length) 
     { 
      return NULL; 
     } 

     if (strncmp(&haystack[i], needle, needle_length) == 0) 
     { 
      return &haystack[i]; 
     } 
    } 
    return NULL; 
} 

Answer 3

我剛剛遇到這個，我想分享我的實施。它認爲它相當快，我沒有任何subcalls。

它返回找到指針的乾草堆中的索引，如果找不到則返回-1。

/* binary search in memory */ 
int memsearch(const char *hay, int haysize, const char *needle, int needlesize) { 
    int haypos, needlepos; 
    haysize -= needlesize; 
    for (haypos = 0; haypos <= haysize; haypos++) { 
     for (needlepos = 0; needlepos < needlesize; needlepos++) { 
      if (hay[haypos + needlepos] != needle[needlepos]) { 
       // Next character in haystack. 
       break; 
      } 
     } 
     if (needlepos == needlesize) { 
      return haypos; 
     } 
    } 
    return -1; 
}