C 语言字符串搜索

C语言字符串搜索

简介

在C语言中，字符串搜索是指在一个字符串（称为主字符串或目标字符串）中查找另一个字符串（称为子字符串或模式）的过程。字符串搜索是编程中的常见任务，广泛应用于文本处理、数据分析和系统编程等领域。C语言提供了多种方法来实现字符串搜索，包括标准库函数和自定义算法。

标准库函数

C语言的标准库 `<string.h>` 提供了几个用于字符串搜索的函数：

strstr()

`strstr()` 函数用于在主字符串中查找子字符串的第一次出现。如果找到，返回指向子字符串首次出现位置的指针；否则返回 `NULL`。

语法

char *strstr(const char *haystack, const char *needle);

• `haystack`：主字符串。
• `needle`：要搜索的子字符串。

示例

#include <stdio.h>
#include <string.h>

int main() {
    const char *haystack = "Hello, world! Welcome to C programming.";
    const char *needle = "world";

    char *result = strstr(haystack, needle);

    if (result != NULL) {
        printf("子字符串找到的位置: %s\n", result);
    } else {
        printf("子字符串未找到。\n");
    }

    return 0;
}

输出

子字符串找到的位置: world! Welcome to C programming.

strchr() 和 strrchr()

`strchr()` 和 `strrchr()` 用于在字符串中搜索单个字符：

• `strchr()`：查找字符的第一次出现。
• `strrchr()`：查找字符的最后一次出现。

示例

#include <stdio.h>
#include <string.h>

int main() {
    const char *str = "This is a sample string.";
    char ch = 's';

    char *first = strchr(str, ch);
    char *last = strrchr(str, ch);

    printf("第一次出现 '%c' 的位置: %s\n", ch, first);
    printf("最后一次出现 '%c' 的位置: %s\n", ch, last);

    return 0;
}

输出

第一次出现 's' 的位置: s is a sample string.
最后一次出现 's' 的位置: string.

自定义字符串搜索算法

除了标准库函数，还可以实现自定义的字符串搜索算法，如朴素搜索算法或更高效的KMP算法。

朴素搜索算法

朴素搜索算法通过逐个字符比较来查找子字符串。

实现

#include <stdio.h>
#include <string.h>

int naive_search(const char *haystack, const char *needle) {
    int haystack_len = strlen(haystack);
    int needle_len = strlen(needle);

    for (int i = 0; i <= haystack_len - needle_len; i++) {
        int j;
        for (j = 0; j < needle_len; j++) {
            if (haystack[i + j] != needle[j]) {
                break;
            }
        }
        if (j == needle_len) {
            return i; // 返回匹配的起始位置
        }
    }
    return -1; // 未找到
}

int main() {
    const char *haystack = "Hello, world!";
    const char *needle = "world";

    int pos = naive_search(haystack, needle);

    if (pos != -1) {
        printf("子字符串找到的位置: %d\n", pos);
    } else {
        printf("子字符串未找到。\n");
    }

    return 0;
}

输出

子字符串找到的位置: 7

KMP算法

KMP（Knuth-Morris-Pratt）算法通过预处理模式字符串来避免不必要的比较，提高搜索效率。

实现

#include <stdio.h>
#include <string.h>

void compute_lps(const char *needle, int *lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    int needle_len = strlen(needle);

    while (i < needle_len) {
        if (needle[i] == needle[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmp_search(const char *haystack, const char *needle) {
    int haystack_len = strlen(haystack);
    int needle_len = strlen(needle);

    int lps[needle_len];
    compute_lps(needle, lps);

    int i = 0, j = 0;
    while (i < haystack_len) {
        if (needle[j] == haystack[i]) {
            i++;
            j++;
        }
        if (j == needle_len) {
            return i - j; // 返回匹配的起始位置
        } else if (i < haystack_len && needle[j] != haystack[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1; // 未找到
}

int main() {
    const char *haystack = "ABABDABACDABABCABAB";
    const char *needle = "ABABCABAB";

    int pos = kmp_search(haystack, needle);

    if (pos != -1) {
        printf("子字符串找到的位置: %d\n", pos);
    } else {
        printf("子字符串未找到。\n");
    }

    return 0;
}

输出

子字符串找到的位置: 10

实际应用案例

字符串搜索在以下场景中非常有用： 1. 文本编辑器：查找和替换功能。 2. 数据分析：从日志文件中提取特定信息。 3. 编译器设计：解析源代码中的关键字。

示例：日志文件搜索

假设有一个日志文件，需要查找包含 "ERROR" 的行：

#include <stdio.h>
#include <string.h>

void search_errors(const char *filename) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        perror("无法打开文件");
        return;
    }

    char line[256];
    while (fgets(line, sizeof(line), file)) {
        if (strstr(line, "ERROR") != NULL) {
            printf("%s", line);
        }
    }

    fclose(file);
}

int main() {
    search_errors("app.log");
    return 0;
}

性能比较

以下是不同搜索算法的时间复杂度：

• `strstr()`：通常为 $O(n\times m)$，但某些实现可能优化。
• 朴素算法：$O(n\times m)$。
• KMP算法：$O(n+m)$（预处理时间 $O(m)$）。

总结

C语言提供了多种字符串搜索方法，从简单的标准库函数到高效的自定义算法。选择合适的方法取决于具体需求，如性能、代码复杂度和可维护性。初学者可以从 `strstr()` 开始，而高级用户可能需要实现更高效的算法（如KMP）以处理大规模数据。

参见

• C语言字符串操作
• C语言指针
• 算法与数据结构