c語言-關於C語言OJ的一道題:Time Limit Exceeded

關於C語言OJ的一道題:Time Limit Exceeded

hihoCoder上的一道關於KMP算法的一道題，題目描述如下：
#1015 : KMP算法
時間限制:1000ms
單點時限:1000ms
內存限制:256MB
描述
小Hi和小Ho是一對好朋友，出生在信息化社會的他們對編程產生了莫大的興趣，他們約定好互相幫助，在編程的學習道路上一同前進。

這一天，他們遇到了一只河蟹，於是河蟹就向小Hi和小Ho提出了那個經典的問題：“小Hi和小Ho，你們能不能夠判斷一段文字（原串）裡面是不是存在那麼一些……特殊……的文字（模式串）？”

小Hi和小Ho仔細思考了一下，覺得只能想到很簡單的做法，但是又覺得既然河蟹先生這麼說了，就肯定不會這麼容易的讓他們回答了，於是他們只能說道：“抱歉，河蟹先生，我們只能想到時間復雜度為（文本長度 * 特殊文字總長度）的方法，即對於每個模式串分開判斷，然後依次枚舉起始位置並檢查是否能夠匹配，但是這不是您想要的方法是吧？”

河蟹點了點頭，說道：”看來你們的水平還有待提高，這樣吧，如果我說只有一個特殊文字，你能不能做到呢？“

小Ho這時候還有點暈暈乎乎的，但是小Hi很快開口道：”我知道！這就是一個很經典的模式匹配問題！可以使用KMP算法進行求解！“

河蟹滿意的點了點頭，對小Hi說道：”既然你知道就好辦了，你去把小Ho教會，下周我有重要的任務交給你們！“

”保證完成任務！”小Hi點頭道。

提示一：KMP的思路

提示二：NEXT數組的使用

提示三：如何求解NEXT數組

輸入
第一行一個整數N，表示測試數據組數。

接下來的N*2行，每兩行表示一個測試數據。在每一個測試數據中，第一行為模式串，由不超過10^4個大寫字母組成，第二行為原串，由不超過10^6個大寫字母組成。

其中N<=20

輸出
對於每一個測試數據，按照它們在輸入中出現的順序輸出一行Ans，表示模式串在原串中出現的次數。

樣例輸入
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
樣例輸出
3
1
3
1
0

這是我按照自己的理解提交的代碼：
#include
#include
#include

int KMP(char *ori,char *pat);

int main(void)
{
char *ori,strori[10001];
char *pat,strpat[1000001];
int n;//測試組數

pat=strpat;//必須初始化 有所指向才行
ori=strori;
scanf("%d\n",&n);
while(n--)
{
    scanf("%s",pat);
    scanf("%s",ori);
    printf("%d\n",KMP(ori,pat));
}
return 0;

}

int KMP(char *ori,char *pat)
{
char *temp,*p;
int num=strlen(pat);
int i=0,j=0;
int *next;
int sum=0;

//求出next數組
next=(int *)malloc(num*sizeof(int));
memset((int *)next,0,num*sizeof(int));
p=temp=pat;
pat++;
while(*pat)
{
if(*pat==*temp)
{
*(next+i+1)=j+1;
pat++;
temp++;
j++;
}
else
{
pat++;
j=0;
}
i++;
}

//匹配字符串
pat=temp=p;
i=j=0;
while(*ori)
{
if(*ori!=*pat)
{
ori++;
if(i!=0)//表明之前有匹配成功過，但還未完全匹配
{
ori=ori-1-*(next+i-1);//ori=ori-i-1+(i-*(next+i-1));
pat=p;
i=0;
}
}

    else
    {
        ori++;
        pat++;
        i++;
        if(*pat=='\0')
        {
            sum++;
            ori=ori-1-*(next+i-1);
            pat=p;
            i=0;
        }
    }
}
return sum;

}

但每次提交結果都是：
Time Limit Exceeded TLE 用戶程序運行時間超過題目的限制
怎麼優化一下我的代碼才能是它AC啊？！求大神指導啊。

最佳回答：

kmp算法，求next數組是有一個小優化的，前兩天剛學習總結了一下，這是鏈接：
http://blog.csdn.net/henuyx/article/details/44653799