实验三串的模式匹配
一、实验目的
1．利用顺序结构存储串，并实现串的匹配算法。

2．掌握简单模式匹配思想，熟悉KMP算法。

二、实验要求
1．认真理解简单模式匹配思想，高效实现简单模式匹配；
2．结合参考程序调试KMP算法，努力算法思想；
3．保存程序的运行结果，并结合程序进行分析。

三、实验内容
1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；
2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。

参考程序:
#include "stdio.h"
void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/
{
int i=1,j=0;
next[1]=0;
while(i<=9)//t[0]
{
if(j==0||t[i]==t[j])
{++i; ++j; next[i]=j; }
else
j=next[j];
}
}
void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */
{
int i=1, j = 0;
next[1]= 0; /* 初始化 */
while (i<=9) /* 计算next[i+1] t[0]*/
{
while (j>=1 && t[i] != t[j] )
j = next[j];
i++; j++;
if(t[i]==t[j]) next[i] = next[j];
else next[i] = j;
}
}
void main()
{
char *p="abcaababc";
int i,str[10];
GetNext1(p,str);
printf("\n");
for(i=1;i<10;i++)
printf("%d",str[i]);
GetNext2(p,str);
printf("\n");
for(i=1;i<10;i++)
printf("%d",str[i]);
printf("\n\n");
}。