C语言KMP算法实现：支持大小写敏感查找

C语言KMP算法实现：支持大小写敏感查找

本文提供了一个修改后的KMP算法实现，它可以通过参数 isCaseSensitive 指定是否大小写敏感进行字符串查找。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

// KMP 算法实现，支持大小写敏感查找
int kmp(const char* s, const char* p, int isCaseSensitive) {
    int n = strlen(s), m = strlen(p);
    int* next = (int*)malloc(sizeof(int) * (m + 1));
    int j = 0, k = -1;
    next[0] = -1;
    while (j < m) {
        if (k == -1 || (isCaseSensitive ? p[j] == p[k] : tolower(p[j]) == tolower(p[k]))) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
    j = 0, k = 0;
    while (j < n && k < m) {
        if (k == -1 || (isCaseSensitive ? s[j] == p[k] : tolower(s[j]) == tolower(p[k]))) {
            j++;
            k++;
        } else {
            k = next[k];
        }
    }
    free(next);
    if (k == m) return j - m;
    else return -1;
}

// 在字符串 haystack 中查找第一次出现 needle 的位置，返回指向该位置的指针，如果找不到则返回 null
char* strstrKMP(char* haystack, const char* needle, int isCaseSensitive) {
    if (isCaseSensitive) {
        return strstr(haystack, needle);
    }
    if (!haystack || !needle || !*needle) {
        return haystack;
    }
    int pos = kmp(haystack, needle, isCaseSensitive);
    if (pos == -1) return NULL;
    else return haystack + pos;
}

char* replaceCstr(const char* allStr, const char* searchStr, const char* replaceStr, int isCaseSensitive, char* result) {
    if (!allStr || !searchStr || !replaceStr || !*searchStr) {
        return (char*)allStr;
    }

    size_t searchStrLength = strlen(searchStr);
    size_t replaceStrLength = strlen(replaceStr);
    size_t count = 0;
    char* p = (char*)allStr;
    char* q = result;

    while ((p = strstrKMP(p, searchStr, isCaseSensitive)) != NULL) {
        count++;
        p += searchStrLength;
    }

    if (count == 0) {
        strcpy(result, allStr);
        return result;
    }

    size_t newStrLength = strlen(allStr) + count * (replaceStrLength - searchStrLength);

    p = (char*)allStr;

    while (count-- > 0) {
        char* r = strstrKMP(p, searchStr, isCaseSensitive);
        long length = r - p;

        memcpy(q, p, length);
        q += length;

        memcpy(q, replaceStr, replaceStrLength);
        q += replaceStrLength;

        p = r + searchStrLength;
    }

    strcpy(q, p);

    return result;
}

int main() {
    clock_t start = clock();

    char str[] = "hello, world!";
    char result[256];
    char* oldptr = str;
    char* now = NULL;

    for (int ii = 0; ii < 10000000; ii++) {
        now = replaceCstr(oldptr, "o", "O", 1, result);
        oldptr = now;
        now = replaceCstr(oldptr, "l", "1", 1, result);
        oldptr = now;
        now = replaceCstr(oldptr, ",", "", 1, result);
        oldptr = now;
        now = replaceCstr(oldptr, "!", "", 1, result);
        oldptr = now;
    }

    clock_t end = clock();
    double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
    printf("C语言程序运行时间  ：%f\n", time_spent);

    return 0;
}

使用方法

在调用 kmp 函数时，将 isCaseSensitive 参数传入即可：

int pos = kmp(haystack, needle, isCaseSensitive);

其中 isCaseSensitive 为 1 表示大小写敏感，为 0 表示大小写不敏感。

示例

char* haystack = "Hello, world!";
char* needle = "world";

// 大小写敏感查找
int pos1 = kmp(haystack, needle, 1);
printf("大小写敏感查找：%d\n", pos1); // 输出：-1

// 大小写不敏感查找
int pos2 = kmp(haystack, needle, 0);
printf("大小写不敏感查找：%d\n", pos2); // 输出：7

总结

本文提供的修改后的KMP算法实现可以根据参数 isCaseSensitive 指定是否大小写敏感进行字符串查找。该算法效率高，适用范围广，希望对大家有所帮助。