kmp算法

//前缀表建立
    void pre_table(char pattern[],int prefix[],int n )
    {
        //pattern 是题目的测的字符串，prefix是前缀表 n是字符串长度
        int len = 0 ; //前缀表每个元素 前后缀相同的个数
        prefix[0] = 0; //前缀表第一个默认为0；
        int i = 1; //前缀表 遍历的下标  因为第一个为0 就从1开始
        
        while(i < n)
        {
            if(pattern[i] == pattern[len])
            {
                //如果下标与前缀表 第len个元素相同时   就是len相同长度加1
                len++;
                prefix[i] = len;
                i++; //继续向下遍历
                
            }
            else{
                if(len > 0)  //如果不相同 就得进行回溯操作
                {
                    len = prefix[len-1]; //前缀表偏移到前一个元素 记录len的长度
                }
                else  //此时 len == 0 了
                {
                    prefix[i] = len;//如果len 一直回溯到0的话 前缀表的该元素为0 
                    i++;
                }
            }
        }
    }
    
    //把前缀表的第一个元素填充为-1，然后最后一个元素舍去 进行数组偏移
    void move_prefix_table(int prefix[],int n)
    {
        int i;
        for(i = n-1; i>0; i--)
        {
             prefix[i] = prefix[i-1];
        }
        prefix[0] = -1;
    }
    //s 为模板 ，T为文本
int kmp(char* S, char* T ) {
    // write code here
    int num = 0;
    int m = strlen(T);  //文本的长度
    int n = strlen(S);  //模板的长度
    int *prefix = malloc(sizeof(int) * n); //给前缀表开辟空间
    pre_table(T,prefix,n);
    move_prefix_table(prefix,n);
    int i=0,j=0;
    while(i<m)
    {
        if(j ==n-1 && S[j] == T[i])
        {
            num++;
            j = prefix[j];
        }
        else if(S[j] == T[i])
        {
            i++;j++;
        }
        else
        {
            j = prefix[j];
            if(j == -1)
            {
                i++; j++;
            }
        }
    }
    return num;
}