一个非空结尾字符串的strstr()函数

Question

我该如何在C语言中实现对计数字符串（即非空终止字符串）进行原地等效的strstr()操作？

- user541686

---

你需要编写自己的版本。 - Seth Carnegie

哪个字符串没有以空字符结尾？被搜索的字符串还是子字符串？ - user142162

@SethCarnegie：这并不是一件简单的事情...如果我真的需要，我可以尝试KMP或其他算法，但如果可能的话，我宁愿避免使用它。 - user541686

你可以从BSD中窃取strnstr()的实现，但要注意这个Bug：http://www.mikeash.com/pyblog/dont-use-strnstr.html。 - Matt K

glibc有memmem函数（可以同时计算needle和haystack的数量），我相信也会有公共领域的实现版本。 - M.M

Answer 1

看看下面的函数是否适用于您。我没有进行充分测试，所以建议您自行测试。

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

- user142162

---

@Mehrdad：也许看一下这个实现也是值得的：http://src.gnu-darwin.org/src/lib/libc/string/strnstr.c.html - user142162

哇，我想我错了...所以strstr通常被定义为O(mn)操作吗？谢谢你指出来...那么我可能会稍后接受这个答案，因为它是问题的确切替代品。 - user541686

@Mehrdad：我稍微整理了一下我的解决方案，如果你想再看一下的话。 - user142162

@Mehrdad C语言没有指定/定义strstr()的O()。 - chux - Reinstate Monica

还可以通过以下方式优化这样的实现：1）使用memcmp避免对strncmp进行NUL检查。2）使用memchr在干草堆中查找针头的第一个字符，这样您就不必为每个字符调用strncmp/memcmp函数（可能将调用次数减少50倍-100倍）。或者跳过memchr，在调用strncmp/memcmp之前手动测试第一个字符。 - ShadowRanger

Answer 2

如果您担心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;
}

- Daniel Fischer

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

- Alex

---

应该趁机把它改成 Boyer-Moore 算法 ;) - dyasta

Answer 4

我使用了这个方法

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

- Jeremiah