场景

当有一段已知足够长的字符串T以及一段相对而言较小的字符串P，而问题是要让你统计P在T中出现的次数或者位置等这类匹配的问题。由于朴素匹配的时间复杂度不足以解决该问题时，可以尝试用kmp匹配算法。

原理及算法过程

我们发现朴素匹配算法之所以复杂度高，是因为做了许多不必要的回溯查找，而这些回溯过程，如果有存在循环节，则直接从循环节的对称点开始匹配，这样就把一些不必要的回溯跳过了。而这些不必要的匹配必须要用一个next数组记录，而每个元素的含义时匹配串到当前长度的字串的前缀和后缀相同的最大长度。规定前缀长度为1的字串next = 0.

  1. 求next数组
  2. 右偏移一位，和匹配串相同大小的next值舍去，next[0]=-1
  3. kmp搜索

模板

写法1:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * ABABCABAA
 * A                    0
 * A B                  0
 * A B A                1
 * A B A B              2
 * A B A B C            0
 * A B A B C A          1
 * A B A B C A B        2
 * A B A B C A B A      3
 * A B A B C A B A A    1
 */

int prefix[10000];  //next
char pattern[10001]={"ABABCABAA"};
char str[1000001];

//得到前缀表数组
void get_prefix_table (char pattern[], int next[], int n) {
    int i=1,len=0;
    next[0] = 0;
    while (i < n) {
        if(pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        }else {
            if(len>0) {
                len = next[len-1];
            }else {
                next[i] = len;
                i++;
            }
        }
    }
}

void move_prefix_table (int next[], int n) {
    for (int i = n-1; i > 0; i--) {
        next[i]=next[i-1];
    }
    next[0] = -1;
}

void kmp_search (char text[], char pattern[]) {
    int n = strlen(text);
    int m = strlen(pattern);
    int *prefix = (int *)malloc(m * sizeof(int));

    get_prefix_table(pattern, prefix, m);
    move_prefix_table(prefix, m);

    printf("prefix table: {");
    for(int i = 0; i < m; i++) {
        printf("%d ", prefix[i]);
    }
    printf("}\n");

    int i = 0;
    int j = 0;
    while(i < n) {
        printf("i = %d, j = %d\n", i, j);
        if(j == m-1 && text[i] == pattern[j]) {
            printf("Found pattern is : %d\n", i-j);
            j = prefix[j];
        }
        if(text[i] == pattern[j]) {
            i++;
            j++;
        }else {
            j = prefix[j];
            if(j == -1) {
                j++;
                i++;
            }
        }
    }
    free(prefix);
}

int main() {
    kmp_search("ABABCBABABCABACABABCABAABABCABAA","ABABCABAA");
    return 0;
}
写法2：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * ABABCABAA
 * A                    0
 * A B                  0
 * A B A                1
 * A B A B              2
 * A B A B C            0
 * A B A B C A          1
 * A B A B C A B        2
 * A B A B C A B A      3
 * A B A B C A B A A    1
 */

int prefix[10001];  //next
char pattern[10001]={"ABABCABAA"};
char str[1000001];

//得到前缀表数组
void get_prefix_table (char pattern[], int next[], int n) {
    int i=0,len=-1;
    next[0] = -1;
    while (i < n) {
        if(len == -1 || pattern[i] == pattern[len]) {
            len++;
            i++;
            next[i] = len;
        }else {
            len = next[len];
        }
    }
}

void kmp_search (char text[], char pattern[]) {
    int n = strlen(text);
    int m = strlen(pattern);

    get_prefix_table(pattern, prefix, m);

    int i = 0;
    int j = 0;
    while(i < n) {
        if(j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        }else {
            j = prefix[j];
        }
        if(j == m) {
            printf("Found pattern is : %d\n", i-j);
            j = prefix[j];
        }//匹配成功,根据情况更改条件，以及内部操作，注意时prefix[j-1]而不是prefix[j]!避免越界
    }
}

int main() {
    kmp_search("ABABCBABABCABACABABCABAABABCABAA","ABABCABAA");
    return 0;
}