正文

揭秘C语言匹配技巧：提升代码效率，轻松掌握匹配次数奥秘

/0 浏览量
0412

在C语言编程中，匹配技巧是一项至关重要的技能。它不仅能够帮助我们提升代码的效率，还能让我们更好地理解程序运行的奥秘。本文将深入探讨C语言中的匹配技巧，帮助你轻松掌握匹配次数的奥秘。

1. 字符串匹配算法

在C语言中，字符串匹配算法是进行匹配操作的基础。常见的字符串匹配算法有：

1.1. Brute Force算法

Brute Force算法是最简单的字符串匹配算法，其基本思想是逐个比较字符串中的字符，直到找到匹配项或遍历完整个字符串。其时间复杂度为O(n*m)，其中n和m分别为待匹配字符串和模式字符串的长度。

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

int brute_force_match(const char *text, const char *pattern) {
    int i, j;
    for (i = 0; text[i] != '\0'; ++i) {
        for (j = 0; pattern[j] != '\0'; ++j) {
            if (text[i + j] != pattern[j]) {
                break;
            }
        }
        if (pattern[j] == '\0') {
            return i; // 匹配成功，返回匹配位置
        }
    }
    return -1; // 匹配失败
}

int main() {
    const char *text = "Hello, world!";
    const char *pattern = "world";
    int position = brute_force_match(text, pattern);
    if (position != -1) {
        printf("Pattern found at position: %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }
    return 0;
}

1.2. KMP算法

KMP算法（Knuth-Morris-Pratt）是一种改进的字符串匹配算法，通过预处理模式字符串来避免重复比较。其时间复杂度为O(n+m)，其中n和m分别为待匹配字符串和模式字符串的长度。

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

void compute_lps_array(const char *pattern, int *lps, int m) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmp_match(const char *text, const char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    int *lps = (int *)malloc(m * sizeof(int));
    compute_lps_array(pattern, lps, m);

    int i = 0, j = 0;
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == m) {
            free(lps);
            return i - j; // 匹配成功，返回匹配位置
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    free(lps);
    return -1; // 匹配失败
}

int main() {
    const char *text = "ABABDABACDABABCABAB";
    const char *pattern = "ABABCABAB";
    int position = kmp_match(text, pattern);
    if (position != -1) {
        printf("Pattern found at position: %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }
    return 0;
}

1.3. Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，其核心思想是利用坏字符规则和好后缀规则。其平均时间复杂度为O(n+m)，其中n和m分别为待匹配字符串和模式字符串的长度。

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

void compute_bad_char_table(const char *pattern, int m, int bad_char[256]) {
    for (int i = 0; i < 256; ++i) {
        bad_char[i] = -1;
    }
    for (int i = 0; i < m; ++i) {
        bad_char[(int)pattern[i]] = i;
    }
}

int boyer_moore_match(const char *text, const char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    int bad_char[256];

    compute_bad_char_table(pattern, m, bad_char);

    int s = 0; // 文本字符串的滑动窗口起始位置
    while (s <= (n - m)) {
        int j = m - 1;
        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }
        if (j < 0) {
            return s; // 匹配成功，返回匹配位置
        } else {
            s += (j - bad_char[(int)text[s + j + 1]]);
        }
    }
    return -1; // 匹配失败
}

int main() {
    const char *text = "ABABDABACDABABCABAB";
    const char *pattern = "ABABCABAB";
    int position = boyer_moore_match(text, pattern);
    if (position != -1) {
        printf("Pattern found at position: %d\n", position);
    } else {
        printf("Pattern not found.\n");
    }
    return 0;
}

2. 匹配次数统计

在C语言中，我们可以通过以下方法统计匹配次数：

2.1. 使用循环遍历字符串

通过循环遍历待匹配字符串，并调用匹配算法函数，可以统计匹配次数。

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

int count_matches(const char *text, const char *pattern) {
    int count = 0;
    int position = 0;
    while ((position = kmp_match(text + position, pattern)) != -1) {
        count++;
        position += strlen(pattern);
    }
    return count;
}

int main() {
    const char *text = "ABABDABACDABABCABAB";
    const char *pattern = "ABABCABAB";
    int count = count_matches(text, pattern);
    printf("Pattern found %d times.\n", count);
    return 0;
}

2.2. 使用递归

通过递归调用匹配算法函数，可以统计匹配次数。

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

int count_matches_recursive(const char *text, const char *pattern, int start) {
    int position = kmp_match(text + start, pattern);
    if (position == -1) {
        return 0;
    } else {
        return 1 + count_matches_recursive(text, pattern, start + strlen(pattern));
    }
}

int main() {
    const char *text = "ABABDABACDABABCABAB";
    const char *pattern = "ABABCABAB";
    int count = count_matches_recursive(text, pattern, 0);
    printf("Pattern found %d times.\n", count);
    return 0;
}

3. 总结

通过本文的介绍，相信你已经对C语言中的匹配技巧有了更深入的了解。掌握这些技巧，将有助于你提升代码效率，轻松掌握匹配次数的奥秘。在实际编程过程中，可以根据具体需求选择合适的匹配算法，以达到最佳效果。

-- 展开阅读全文 --