#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*naive string-matching algorithm,T為原始字符串，P為需要匹配的字符串*/
void naiveMatch(char *T,char *P)
{
    int lenT,lenP,i,j;
    lenT=strlen(T);
    lenP=strlen(P);
    if(lenT<lenP)/*需要匹配的字符串比原始字符串還要長出錯*/
    {
        perror("input error");
        return ;
    }
    for(i=0;i<(lenT-lenP+1);i++)
    {
        for(j=0;j<lenP;j++)
        {
            if(T[i+j]!=P[j])
                break;
        }
        if(j==lenP)
            printf("string match at place %d\n",i);
    }
}

/*kmp預處理需要的匹配串*/
void getNext(char *p,int next[])
{
    int len,i,j;
    len=strlen(p);
    next[0]=0;
    for(i=1;i<len;i++)
    {
        j=next[i-1];
        while((p[i-1]!=p[j-1])&&(j!=0))
        {
            j=next[j-1];
//            printf("j= %d\n",j);
        }
        next[i]=j+1;
        printf("next[i]=%d\n",next[i]);
    }
}

/*kmp字符串匹配算法*/
void kmp(char *t,char *p,int next[])
{
    int lent,lenp,i,j;
    lent=strlen(t);
    lenp=strlen(p);
    i=0;
    j=0;
    while(i<(lent))
    {
        if((j==-1)||(t[i]==p[j]))
        {
            i++;
            j++;

//            printf("i=%d,j=%d\n",i,j);
        }
        else
        {
           
//            printf("in else i=%d,j=%d\n",i,j);
            j=next[j]-1;
        }
        if(j==(lenp))
        {
            printf("match at place %d\n",i-lenp);
        }
    }
}

int main()
{
    char p[10]="0001";
    char t[20]="000010001010001";
    naiveMatch(t,p);/*測試普通字符串匹配算法*/
    char p1[10]="abaabcac";
    char t1[20]="acabaabaabcacaabc";
    int len=strlen(p1);
    int *next;
    next=(int*)malloc(sizeof(int)*len);
    getNext(p1,next);
    kmp(t1,p1,next);/*測試kmp算法*/

  
    getNext(p,next);
    kmp(t,p,next);/*測試kmp算法*/
}