假设在文本"ababcabccabccacbab"中查找模式"abccac",c语言KMP算法的串匹配代码

在C语言中，使用Knuth-Morris-Pratt (KMP) 算法进行字符串匹配时，主要是为了提高搜索效率，避免不必要的字符比较。以下是使用KMP算法在给定字符串中查找特定模式`"abccac"`的基本步骤的C代码示例：

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

// 计算Pattern的前缀表
void compute_lps(char pattern[], int lps[]) {
    int len = strlen(pattern);
    int index = 0;
    lps[0] = 0;

    for (int i = 1; i < len; ++i) {
        if (pattern[i] == pattern[index]) {
            index++;
            lps[i] = index;
        } else {
            if (index != 0)
                index = lps[index - 1];
            else
                lps[i] = 0;
        }
    }
}

// KMP算法实现字符串匹配
int kmp_search(char text[], char pattern[]) {
    int len_text = strlen(text);
    int len_pattern = strlen(pattern);
    int lps[len_pattern];
    compute_lps(pattern, lps);

    int index = 0;
    while (index < len_text) {
        if (text[index] == pattern[index]) {
            index++;
        }

        // 如果遇到失败的位置，根据lps数组回溯
        if (index >= len_pattern) {
            return index - len_pattern;  // 找到匹配的位置
        } else if (text[index] != pattern[index]) {
            if (index != 0)
                index = lps[index - 1];
            else
                index++;
        }
    }
    return -1;  // 没有找到匹配
}

int main() {
    char text[] = "ababcabccabccacbab";
    char pattern[] = "abccac";

    int result = kmp_search(text, pattern);
    if (result != -1) {
        printf("Pattern found at position %d\n", result);
    } else {
        printf("Pattern not found in the given text.\n");
    }

    return 0;
}

这段代码首先计算了模式`"abccac"`的前缀函数(lps)，然后在主的`kmp_search`函数中，通过这个前缀函数指导搜索过程，提高了匹配速度。