KMP算法什么意思

Question

  KMP算法什么意思

Answer 1

#include <bits/stdc++.h>using namespace std;/*
 *next[]的含义:x[i-next[i]...i-1] = x[0...next[i]-1] 
 *next[i]为满足x[i-z...i-1] =  z[0...z-1]的最大z值(就是x的自身匹配); 
 */void kmp_pre(char x[], int m, int next[]){    int i, j;
    j = next[0] = -1;
    i = 0;    while(i < m){        while(j != -1 && x[i] != x[j])  j = next[j];
        next[++i] = ++j;
    }
}/*
 *kmpNext[]的意思是:next'[i] = next[next[...[next[i]]](直到next'[i]<0或者x[next'[i]]!=x[i]) 
 *这样的预处理就可以快一些 
 *
 */void preKMP(char x[], int m, int kmpNext[]){    int i, j;
    j = kmpNext[0] = -1;
    i = 0;    while(i < m){        while(-1 != j && x[i] != x[j])  j = kmpNext[j];        if (x[++i] == x[++j])   kmpNext[i] = kmpNext[j];        else    kmpNext[i] = j;
    }
}/*
 *返回x在y中出现的次数, 可以重叠 
 */int next[1010];int KMP_Count(char x[], int m, char y[], int n){    //x是模式串， y是主串 
    int i, j;    int ans = 0;//  preKMP(x, m, next);
    kmp_pre(x, m, next);
    i = j = 0;    while (i < n){        while(j != -1 && y[i] != x[j])  j = next[j];
        i++;
        j++;        if (j >= m){
            ans ++;
            j = next[j];
        }
    }    return ans;
}int main(){    char y[] = "BBCABCDABABCDABCDABDE";    char x[] = "ABCDABD";    cout << KMP_Count(x, strlen(x), y, strlen(y));    return 0;
}