않는 strstr()

Question

어떻게이 에 대한 strstr()의 현재 위치에서 동등한 C에서 (즉 하지 null로 끝나는) 문자열을 계산해야합니까?

Answer 1

- 기본적으로, 당신은 필요가 없습니다, 이러한 경우는 자연적으로 발생하지 않습니다 - 나는 여기에 수정 한 어떤 주위에 내가 거짓말을했던 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

다음 기능이 효과가 있는지 확인하십시오. 나는 그것을 철저히 시험하지 않았으므로 그렇게하도록 권할 것이다. 당신은 O (m의 * n)도 동작을 두려워하는 경우

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

방금이 문제가 발생했습니다. 구현 방법을 공유하고 싶습니다. 그것은 아주 빠르다고 생각합니다. 저는 서브 콜이 없습니다.

바늘이있는 건초 더미에서 색인을 찾지 못하면 -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; 
}