kmp算法

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算模板串S在文本串T中出现了多少次
 * @param S string字符串 模板串
 * @param T string字符串 文本串
 * @return int整型
 */
#include <string.h>
int ne[100000];
void getNext(char* a, int next[])
{
    int j = 0;
    next[0] = 0;
    for(int i = 1; i < strlen(a); i++)
    {
        while(j > 0 && a[i] != a[j])
        {
            j = next[j - 1]; //回到前一个，相当于自身做了一次kmp
        }
        if(a[i] == a[j])
        {
            j++;
        }
        next[i] = j;
    }
}
int kmp(char* S, char* T ) {
    // write code here
    int i = 0 , j = 0, count = 0;
    int slen = strlen(S);
    int tlen = strlen(T);
    getNext(S, ne);
    for(i = 0; i < tlen; i++)
    {
        if(j == 0 && tlen - i < slen)
        break;
        
        while(j > 0 && T[i] != S[j])
        {
            j = ne[j - 1];
        }
        if(T[i] == S[j])
        {
            j++;
        }
        if(j == slen)
        {
            count++;
            j = ne[j - 1];
        }
    }
    return count;
}

还是跑不完，只能跑5组测试用例，数一大还是超时，还望老哥们赐教

//前缀表建立
    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;
}