C语言中的字符串查找算法总结

字符串查找是在给定字符串中搜索指定子串的过程。在C语言中，有多种字符串查找算法可以选择，每种算法都有自己的优缺点。本文将总结C语言中常见的字符串查找算法。

1. 暴力查找算法

暴力查找算法也被称为朴素查找算法或穷举法。它的基本思想是逐个字符地比较目标子串和给定字符串中的字符是否匹配，如果不匹配，则移动到下一个位置进行比较。这种算法的时间复杂度为O(m*n)，其中m是目标子串的长度，n是给定字符串的长度。

int naiveSearch(char* string, char* target) {
    int i, j;
    int stringLen = strlen(string);
    int targetLen = strlen(target);
    
    for (i = 0; i <= stringLen - targetLen; i++) {
        for (j = 0; j < targetLen; j++) {
            if (string[i + j] != target[j])
                break;
        }
        
        if (j == targetLen)
            return i;
    }
    
    return -1;
}

2. KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种利用已匹配的信息避免不必要的比较的字符串查找算法。它的核心思想是利用目标子串中已匹配的字符来确定下一次匹配的位置。这种算法的时间复杂度为O(m+n)，其中m是目标子串的长度，n是给定字符串的长度。

void computeLPSArray(char* target, int targetLen, int* lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;
    
    while (i < targetLen) {
        if (target[i] == target[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int KMPSearch(char* string, char* target) {
    int stringLen = strlen(string);
    int targetLen = strlen(target);
    int* lps = (int*)malloc(targetLen * sizeof(int));
    int i = 0, j = 0;
    
    computeLPSArray(target, targetLen, lps);
    
    while (i < stringLen) {
        if (target[j] == string[i]) {
            j++;
            i++;
        }
        
        if (j == targetLen) {
            free(lps);
            return i - j;
        } else if (i < stringLen && target[j] != string[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    free(lps);
    return -1;
}

3. Boyer-Moore算法

Boyer-Moore算法是一种效率较高的字符串查找算法。它的主要思想是从目标子串的末尾开始进行匹配，并利用匹配失败时可以跳过一定数量的字符，以减少比较次数。这种算法的时间复杂度为O(m+n)，其中m是目标子串的长度，n是给定字符串的长度。

#define CHAR_SIZE 256

void computeBadCharTable(char* target, int targetLen, int* badCharTable) {
    int i;
    
    for (i = 0; i < CHAR_SIZE; i++) {
        badCharTable[i] = -1;
    }
    
    for (i = 0; i < targetLen; i++) {
        badCharTable[(int)target[i]] = i;
    }
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

int BMSearch(char* string, char* target) {
    int stringLen = strlen(string);
    int targetLen = strlen(target);
    int badCharTable[CHAR_SIZE];
    int shift = 0, i, j;
    
    computeBadCharTable(target, targetLen, badCharTable);
    
    while (shift <= (stringLen - targetLen)) {
        j = targetLen - 1;
        
        while (j >= 0 && target[j] == string[shift + j]) {
            j--;
        }
        
        if (j < 0) {
            return shift;
        } else {
            shift += max(1, j - badCharTable[(int)string[shift + j]]);
        }
    }
    
    return -1;
}

总结

以上是C语言中常见的字符串查找算法的总结。根据不同的应用场景和需求，我们可以选择合适的算法来提高字符串查找的效率。在实际应用中，还可以将字符串查找与其他算法结合使用，以达到更好的效果。希望本文对你有所帮助！

本文来自极简博客，作者：冬天的秘密，转载请注明原文链接：C语言中的字符串查找算法总结