在一个较大的字符串中查找子字符串的第一个字符位置

Question

我的问题是需要使用for循环找到一个大字符串中子字符串的数字位置。我不能使用像strstr这样的字符串函数，并且尝试了大多数嵌套for循环的迭代。

基本上，我需要一个循环来查找包含特定子串的字符串，并且如果它与第一个字符匹配，则检查其余字符是否也匹配。

如果一切都匹配，则返回子串第一个字符的位置，如果没有找到，则返回-1。

非常感谢任何帮助。谢谢！

- user4368627

---

你能给我们举一个子字符串和较大字符串的例子吗？你期望返回什么位置？ - RoadRunner

当你说“我无法使用例如strstr的字符串函数”时，你的意思是什么？ - Luis Colorado

Answer 1

正如您所描述的那样，这可以通过2个嵌套循环来完成：

#include <stdlib.h>  // for size_t

int indexof(const char *str, const char *substr) {
    for (size_t i = 0;; i++) {
        /* for every position in the string */
        for (size_t j = 0;; j++) {
            /* check of all characters fro substr match at this offset */
            if (substr[j] == '\0') {
                /* if we reach the end of substr, we have a match at offset i */
                return i;
            }
            if (str[i + j] != substr[j]) {
                /* if there is a mismatch, stop checking and skip to the next offset */
                break;
            }
        }
        if (str[i] == '\0') {
            /* no match found: return -1 */
            return -1;
        }
    }
}

注：

• 该函数被指定为返回int，因为它在没有匹配的情况下返回-1。然而，匹配的偏移量可能不适合在int范围内。如果可以访问超过2GB的数据，则在32位系统上返回类似于POSIX中定义的ssize_t这样的带符号类型并不能完全解决这个问题。

• 通过显式地测试子字符串的第一个字符，该函数可以变得更快。

• 对于长字符串和子字符串，更先进的算法（如Boyer Moore's和Knuth Morris Pratt's）可以运行得更快。

- chqrlie

---

说句实话，使用特定的字符串搜索算法，如KMP算法，可以使这个任务更加高效。 - RoadRunner

我刚刚测试了代码，但忘记提到它也应该适用于带有空格的字符串。能否修改以包括空格？因此，如果我在字符串"The cat is cool"中搜索子字符串"cat"，它将返回整数4，因为它包括空格。 - user4368627

@Monty：包括空格是什么意思？在字符串"The cat is cool"中搜索"cat"，已经可以在偏移量4处找到它了。 - chqrlie