求助！！！！！！！模式匹配和KMP算法

Question

模式匹配和KMP算法
令模式匹配问题中的模式 p 和目标t如下所示（双引号内）
p="13113113111"
t="113113113113113113113113113113113113113113113111311311311311311311"
1. 用字符串数据结构表达 p 与t 字符串（10%）
2. 分别从字符串数据结构打印输出 p 与t （10%）
3. 设计朴素的模式匹配算法，求解模式 p 在目标t的位置，并打印输出（20%）
4. 计算朴素的模式匹配算法的比较次数 （20%）
5. 通过 KMP 算法求解模式在目标的位置，并打印输出（20%）
6. 计算 KMP 算法的比较次数（20%）
（上述“比较次数”为字符比较个数，如p="ab",t="aabcd",朴素模式匹配比较次数为4）

Answer 1

这个题目最难的是KMP算法和实现。其他的书本上都有的。

我自己写的个程序：
测试结果如下：
113113113113113113113113113113113113113113113111311311311311311311
13113113111
at 37

贴上源代码：

#include"stdio.h"
#include "conio.h"
#include "stdio.h"
#include "math.h"

int result;
char pat[]="13113113111";
char str[]="113113113113113113113113113113113113113113113111311311311311311311";
int next[7];

void getNext(char pat[], int next[])
{
int j = 0;
int k = -1;
next[0] = -1;
while (pat[j])
{
if ( k == -1 || pat[j] == pat[k])
{
j++;
k++;
next[j] = k;
}
else
{
k = next[k];
}
}
}
int KMP(char *str1, char*pat, int *next)
{
int i=0,j=0;
while(str[i])
{
if(pat[j]==0)
return i-j;
if(j==0 || str[i]==pat[j])
{
++i;
++j;
}else
j=next[j];
}
if(pat[j]==0)
return i-j;
return -1;
}

int main(int argc, char* argv[])
{
int i;

getNext(pat,next);
result=KMP(str,pat,next);
printf("%s\n",str);
for(i=0;i<result;i++) printf(" ");
printf("%s\n",pat);
printf("at %d\n",result);
getch();
return 0;
}
祝你好运！