写一篇c语言代码用kmp算法实现病毒检查

在C语言中，KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的有效算法，尤其适用于模式串（即病毒特征串）在主串中查找的情况。下面是一个简单的示例，展示如何使用KMP算法编写病毒检测程序：

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

// 定义辅助函数，用于构建部分匹配表
void getPartialMatchTable(char pattern[], int lps[], int m) {
    int i = 0, j = -1;
    lps[0] = 0; // 初始化lps数组的第一个元素为0

    // 遍历模式串，计算最长公共前缀长度
    while (i < m) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            lps[i] = j;
        } else {
            j = lps[j];
        }
    }
}

// KMP搜索主串，返回第一次匹配的位置，如果没有找到则返回-1
int kmpSearch(char mainStr[], char pat[], int n, int m) {
    int i = 0, j = 0;
    int lps[m]; // 存储部分匹配表

    getPartialMatchTable(pat, lps, m);

    while (i < n && j < m) {
        if (pattern[j] == mainStr[i]) {
            i++;
            j++;
        } else if (j != 0) {
            j = lps[j - 1];
        } else {
            i++;
        }
    }

    // 如果找到了匹配，则返回匹配位置，否则返回-1
    return (j == m ? i - j : -1);
}

int main() {
    char mainStr[] = "This is a sample string to test virus detection using KMP algorithm.";
    char pat[] = "virus"; // 假设这是我们正在查找的病毒特征串
    int n = strlen(mainStr), m = strlen(pat);

    // 检查病毒是否存在
    int index = kmpSearch(mainStr, pat, n, m);

    if (index != -1) {
        printf("Pattern found at position %d.\n", index);
    } else {
        printf("Pattern not found in the string.\n");
    }

    return 0;
}

这个程序首先定义了一个部分匹配表（LPS），然后在主串中应用KMP算法寻找特征串。如果找到匹配，它会打印出匹配的位置；否则，表示病毒未被找到。