null-terminal이 아닌 문자열의 strstr()

null-terminal이 아닌 문자열의 strstr()

인플레이스 등가물은 어떻게 해야 하나요?strstr()C의 카운트된 문자열(즉, null-terminated가 아닌 경우)에 대해?

기본적으로 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;
}

아래 기능이 사용자에게 적합한지 확인해보세요.제가 충분히 테스트를 해보지 않았으니, 그렇게 하시길 권합니다.

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

저는 방금 이 사실을 알게 되었고 저의 구현 방법을 공유하고자 합니다.빠른 것 같아요. 서브콜이 없어서요.

바늘이 발견된 건초 더미에서 인덱스를 반환하거나, 발견되지 않은 경우 -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;
}

저는 이 방법을 사용했습니다.

int memsearch(char* dataset, int datasetLength, char* target, int targetLen){
    for(int i = 0; i < datasetLength; i++){
            if(dataset[i] == target[0]){
                    int found = 1;
                    for(int j = 0; j < targetLen; j++){
                            int k = i + j;
                            if(k >= datasetLength || target[j] != dataset[k]){
                                    found = 0;
                                    break;
                            }
                    }
                    if(found) return i;
            }
    }
    return -1;
}

언급URL : https://stackoverflow.com/questions/8584644/strstr-for-a-string-that-is-not-null-terminated