KMP

OI 算法 笔记 字符串

//KMP
//思想是通过预处理减小失配时的代价
//例子：
/*
* s1 : aaaaba
* s2 : aaba
* KMP匹配过程
* aaaaba
* ^
* a^
* aa^
*  aa^ X
*   aa^
*   aab^
*   aaba !!!
*/    
#include<cstdio>
#include<cstring>
const int N = 1000000 + 5;
char s1[N], s2[N];
int len1, len2;
int shift[N];
//shift[j]表示当匹配到 s2 的第 j 个字母而第 j + 1个字母不能匹配了时，新的 j' 最大是多少
int main() {
    scanf("%s\n%s", s1 + 1, s2 + 1);
    int i = 0, j = 0;
    len1 = strlen(s1 + 1); len2 = strlen(s2 + 1);
/************再看这里************/  
/*求shift数组的过程类似于自己和自己匹配*/
/*shift[j]保证了s2中[1 .. shift[j]] == [j - shift[j] + 1 .. j]*/
    shift[1] = 0;
    j = 0;
    for(i = 2; i <= len2; ++i) {
        while(j && s2[i] != s2[j+1])
            j = shift[j];
        if(s2[i] == s2[j+1]) {
            ++j;
        }
        shift[i] = j;
    }
/************先看这里************/ 
/*i是当前匹配到的位置，j是当前匹配的长度*/    
    j = 0;
    for(i = 1; i <= len1; ++i) {
        while(j && s1[i] != s2[j+1]) 
            j = shift[j];/*如果失配，就移动*/ 
        if(s1[i] == s2[j+1]) 
            ++j;/*如果匹配，就增加j*/ 
        if(j == len2) {/*匹配结束*/ 
            printf("%d\n", i - len2 + 1);
            j = shift[j];
        }
    } 
/*现在关键就是如何求shift数组*/ 
    for(int i = 1; i <= len2; ++i) {
        printf("%d ", shift[i]);
    }
    return 0;
}