KMP——字符串匹配算法

KMP算法挺抽象，第一次接触理解不够深，以后通过题目慢慢了解。

设字符串a长度为n，待匹配子串b的长度为m，暴力枚举法的时间复杂度为log(m*n)
而KMP算法的时间复杂度为log(m+n)，因为指向主串i只增不减，避免了多余的回溯。

算法内容：
首先构造一个数组P
P[i]存储的是b串前i个字符前缀和后缀相同的最大字符个数
例如b=“ababa”，则p={0,0,1,2,3}
然后是匹配过程，例如：

若让b向右移动一格是没必要的，利用已经预处理好的数组p可以让b向右移动一个前缀的距离，只需j=p[j]，而p[5]为3，即从i== 5，j== 3开始匹配，如下图

一道例题（HOJ）：剪花布条

#include
using namespace std;
char b[1005],a[1005];

int kmp(char a[],char b[]){//a和b都是从下表为1开始存储！！
    int res=0,j=0,m=strlen(b+1),n=strlen(a+1),p[1005]={0};
    for(int i=1;i0&&b[j+1]!=b[i+1])j=p[j];
            if(b[i+1]==b[j+1])j++;
            p[i+1]=j;
        }
        j=0;
        for(int i=0;i0&&b[j+1]!=a[i+1])j=p[j];
            if(b[j+1]==a[i+1])j++;
            if(j==m){
                //cout<>a+1){
        if(a[1]=='#')break;
        cin>>b+1;
        cout<