strstr() cho một chuỗi đó là KHÔNG null-chấm dứt

Question

Làm thế nào để làm tại chỗ tương đương với strstr() cho một tính chuỗi (ví dụ: không null-terminated) trong C?

Answer 1

Nếu bạn sợ O (m * n) hành vi - về cơ bản, bạn cần không, trường hợp này không xảy ra một cách tự nhiên - đây là một thực hiện KMP tôi đã nằm xung quanh mà tôi đã sửa đổi để lấy chiều dài của đống cỏ khô. Ngoài ra một wrapper. Nếu bạn muốn thực hiện các tìm kiếm lặp lại, hãy tự viết và sử dụng lại mảng borders.

Không đảm bảo cho lỗi-freeness, nhưng dường như vẫn hoạt động.

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

Kiểm tra xem chức năng dưới đây có phù hợp với bạn hay không. Tôi đã không thử nghiệm nó kỹ lưỡng, vì vậy tôi sẽ đề nghị bạn làm như vậy.

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

Tôi vừa mới xem xét điều này và tôi muốn chia sẻ triển khai của mình. Nó nghĩ rằng nó khá nhanh, tôi không có bất kỳ subcalls.

Nó trả về chỉ mục trong haystack nơi kim được tìm thấy hoặc -1 nếu không tìm thấy.

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