引言

在网络时代，保护网络环境，防止敏感词传播显得尤为重要。C语言作为一种高效、稳定的编程语言，被广泛应用于敏感词过滤系统中。本文将详细介绍如何使用C语言编写高效敏感词过滤程序，帮助开发者告别低效代码，轻松守护网络环境。

敏感词过滤原理

敏感词过滤主要基于字符串匹配算法。常见的匹配算法包括：

  • 暴力匹配：逐个字符比较，效率低下。
  • KMP算法：通过预处理模式串，提高匹配效率。
  • Boyer-Moore算法：根据字符出现频率和部分匹配表，跳过无关字符，提高匹配效率。

本文将重点介绍KMP算法和Boyer-Moore算法在敏感词过滤中的应用。

KMP算法

KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法。其核心思想是避免重复比较已经确定不匹配的字符。

KMP算法步骤

  1. 预处理模式串：计算部分匹配表（也称为“next”数组）。
  2. 匹配过程：从主串和模式串的第一个字符开始比较，如果匹配，继续比较下一个字符；如果不匹配，根据部分匹配表调整模式串的位置。

KMP算法代码示例

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

// 计算部分匹配表
void computeNext(char *pattern, int next[]) {
    int len = strlen(pattern);
    next[0] = 0;
    int k = 0;
    for (int i = 1; i < len; i++) {
        while (k > 0 && pattern[k] != pattern[i]) {
            k = next[k - 1];
        }
        if (pattern[k] == pattern[i]) {
            k++;
        }
        next[i] = k;
    }
}

// KMP算法匹配
int KMP(char *text, char *pattern) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);
    int next[len_pattern];
    computeNext(pattern, next);

    int i = 0, j = 0;
    while (i < len_text) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == len_pattern) {
            return i - j;
        } else if (i < len_text && pattern[j] != text[i]) {
            if (j != 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

Boyer-Moore算法

Boyer-Moore算法是一种高效的字符串匹配算法，其核心思想是利用字符出现频率和部分匹配表跳过无关字符。

Boyer-Moore算法步骤

  1. 构建部分匹配表：计算部分匹配表（也称为“bad character shift”数组）。
  2. 构建好后缀规则表：计算好后缀规则表（也称为“good suffix shift”数组）。
  3. 匹配过程：根据部分匹配表和好后缀规则表调整模式串的位置。

Boyer-Moore算法代码示例

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

// 构建部分匹配表
void buildBadCharShift(char *pattern, int badCharShift[]) {
    int len = strlen(pattern);
    for (int i = 0; i < 256; i++) {
        badCharShift[i] = len;
    }
    for (int i = 0; i < len; i++) {
        badCharShift[(unsigned char)pattern[i]] = len - i - 1;
    }
}

// 构建好后缀规则表
void buildGoodSuffixShift(char *pattern, int goodSuffixShift[]) {
    int len = strlen(pattern);
    int i = len - 1, j = len;
    goodSuffixShift[len] = j;
    while (i > 0) {
        while (j > 0 && pattern[i] != pattern[j - 1]) {
            if (goodSuffixShift[j] == 0) {
                goodSuffixShift[i] = j;
                break;
            }
            j = goodSuffixShift[j];
        }
        j--;
        i--;
        goodSuffixShift[i] = j;
    }
}

// Boyer-Moore算法匹配
int BoyerMoore(char *text, char *pattern) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);
    int badCharShift[256];
    int goodSuffixShift[len_pattern + 1];
    buildBadCharShift(pattern, badCharShift);
    buildGoodSuffixShift(pattern, goodSuffixShift);

    int s = 0;
    while (s <= len_text - len_pattern) {
        int i = len_pattern - 1;
        while (i >= 0 && pattern[i] == text[s + i]) {
            i--;
        }
        if (i < 0) {
            return s;
        } else {
            s += (i < badCharShift[(unsigned char)text[s + i]]) ? i - badCharShift[(unsigned char)text[s + i]] : goodSuffixShift[i + 1];
        }
    }
    return -1;
}

总结

本文介绍了KMP算法和Boyer-Moore算法在敏感词过滤中的应用。通过使用这些高效的字符串匹配算法，开发者可以轻松实现敏感词过滤程序，提高网络环境的安全性。在实际应用中，可以根据具体需求选择合适的算法，以达到最佳效果。