搜索子串

在字符串s内搜索子串p，返回首次匹配的起始位置，否则返回-1

(1)朴素的解决办法

int search(char *s,char *p){
    int m,n,i,j,k;
    m=strlen(s);
    n=strlen(n);
    for(i=0;i<=m-n;i++)
        for(j=i,k=0;k<n && s[j]==p[k];j++,k++)
          if(k==n) return i;
    return -1;
}

(2)KMP算法

void kmp(char *,char *);
static void getnext(int *,char *,int);

void
kmp(char *s,char *p){
    int *f,m,n,i,t;
    f=(int *)malloc(sizeof(int)*n);
    getnext(f,p,n);
    for(i=0,t=0;i<m && t;){
        if(s[i]==p[t]) { i++;t++;}
        else if(t==0) i++;
        else t=f[t];
    }

    free(f);
    if(t==n) return i-n;
    return -1;
}

static void
getnext(int *f,char *p,int n){
    int i,t;
    f[0]=0;
    for(i=1,t=0;i<n;i++){
        while(t>0 && p[i]!=p[t]) t=f[t];
        if(p[i]==p[t]) f[i]=++t;
        else f[i]=0;
    }
}