Sunday算法计算串匹配比较次数C语言代码实现

Sunday算法是一种用于优化KMP（Knuth-Morris-Pratt）字符串搜索算法的改进版本，它通过预处理模式串，减少了比较次数。这个算法主要是为了减少无效的字符比较，避免了每次都在主串和模式串中逐个字符对比的情况。

以下是使用C语言实现Sunday算法的一个简化版代码：

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

void computeSundayTable(char* pattern) {
    int length = strlen(pattern);
    int lps[length + 1];
    
    for (int i = 1; i <= length; ++i) {
        lps[i] = 0;
        
        if (i > 0 && pattern[i - 1] == pattern[lps[i - 1]]) {
            lps[i] = lps[i - 1] + 1;
        }
    }
    
    // 输出lps数组用于调试
    for (int i = 0; i <= length; ++i) {
        printf("%d ", lps[i]);
    }
    printf("\n");
}

int sundaySearch(char* text, char* pattern) {
    int textLength = strlen(text);
    int patternLength = strlen(pattern);
    int lps[patternLength + 1];
    computeSundayTable(pattern);
    
    int index = 0;
    for (int i = 0; i < textLength; ++i) {
        if (index > 0 && pattern[index] != text[i]) {
            index = lps[index - 1];
        }
        else if (pattern[index] == text[i]) {
            index++;
        }

        if (index == patternLength) {
            printf("Pattern found at position %d\n", i - patternLength + 1);
            index = lps[index - 1]; // 如果找到了，跳过之前的字符
        }
    }
}

int main() {
    char pattern[] = "ababc";
    char text[] = "ababcabc";
    sundaySearch(text, pattern);
    return 0;
}

在这个代码中，`computeSundayTable`函数计算了模式串的Longest Proper Prefix which is also a Suffix (lps)，即最长公共前后缀长度。然后在`sundaySearch`函数中，我们利用lps数组进行查找，当遇到不匹配的字符时，会直接跳到上次匹配的lps位置继续查找，从而提高效率。