字符串匹配算法

#include <cstdio>
#include <cstring>

int brute_force(const char *text, const char *str) {
    for(int i = 0; text[i]; i++) {
        int miss_match = 0;
        for(int j = 0; str[j]; j++) {
            if(text[i + j] == str[j]) continue;
            miss_match = 1;
            break;
        }
        if(miss_match == 0) return i;
    }
    return -1;
}

//要在已成功匹对的字符串中找到真后缀与真前缀相等的最长情况，才能使得模式串移动位数最少（可通过假设模式串应移动1位，移动2位……一步一步归纳总结出该结论）
//next[j]记录了从下标0到下标j-1这一字符串中，使真后缀与真前缀相等时可以达到的最大长度
int kmp(const char *text, const char *str) {
    //1. init next
    //str[i-j]~str[i]是模式串的后缀，str[0]~str[j]是模式串的前缀
    int next[100] = {0};
    for(int i = 1, j = 0; str[i];) {
        while(j != 0 && str[j] != str[i]) { j = next[j]; }
        if(str[j] == str[i]) j++;
        next[++i] = j;
    }
    //2. match string
    //i是目标串的指针，j是模式串的指针
    for(int i = 0, j = 0; text[i]; i++) {
        while(j != 0 && str[j] != text[i]) { j = next[j]; }
        if(str[j] == text[i]) j++;
        if(str[j] == '\0') return (i + 1) - j; //此时j为模式串的长度
    } 
    return -1;
}

int sunday(const char *text, const char *str) {
    int len_text = strlen(text), len_str = strlen(str);
    int ind[128];
    for(int i = 0; i < 128; i++) ind[i] = len_str + 1; //若该字符从未出现的缺省距离
    for(int i = 0; str[i]; i++) ind[str[i]] = len_str - i; //该字符最后一次出现时到'\0'的距离
    int i = 0;
    while(i + len_str <= len_text) {
        int miss_match = 0;
        for(int j = 0; str[j]; j++) {
            if(text[i + j] == str[j]) continue;
            miss_match = 1;
            break;
        }
        if(miss_match == 0) return i;
        i += ind[text[i + len_str]]; //令模式串直接移动到能与“文本串中正对模式串'\0'的字符”进行匹对的位置
    }
    return -1;
}

int main() {
    char text[100], str[100];
    scanf("%s%s", text, str);
    printf("%d\n", brute_force(text, str));
    printf("%d\n", kmp(text, str));
    printf("%d\n", sunday(text, str));
    return 0;
}

总结：

1. BF算法和sunday算法中的“i”总是指向模式串的第一个字符，所以是通过“i”来移动模式串的；
2. 而KMP算法中的“i”则指向模式串中最长前缀的后一个字符，故KMP算法是通过减小“j”，同时令“j”与“i”对齐来移动模式串的。