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