Question

数据结构里实现KMP算法

求个程序，实现KMP算法，输入三组主串S和模式串P，输出模式串的Next(j)函数值，以及该P在S中的位置的定位函数值，即序号值。其中S的长度为15~25,P的长度为5~8。

Answer 1

通常情况下，我们会按照结构模型把系统产生的数据分为三种类型：结构化数据、半结构化数据和非结构化数据。结构化数据，即行数据，是存储在数据库里，可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据，它们可以某种标准格式存在于文件或记录的固定字段中。相对应的，没有固定结构不方便用数据库二维逻辑表来表现的数据即称为非结构化数据，包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。我们都知道，结构化的数据很容易被采集和存储，分析展示起来也很容易，市场上已经有很多成熟的BI…

Answer 2

KMP算法的C语言实现2007-12-10 23:33

基本思想：
这种算法是D.E.Knuth 与V.R.Pratt和J.H.Morris同时发现的，因此人们称为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。

#include <stdio.h>
#include <string.h>
int index_KMP(char *s,char *t,int pos);
void get_next(char *t,int *);

char s[10]="abcacbcba";
char t[4]="bca";
int next[4];
int pos=0;

int main()
{
int n;
get_next(t,next);
n=index_KMP(s,t,pos);
printf("%d",n);
return 0;
}

int index_KMP(char *s,char *t,int pos)
{
int i=pos,j=1;
while (i<=(int)strlen(s)&&j<=(int)strlen(t))
{
if (j==0||s[i]==t[j-1])
{
i++;
j++;
}
else j=next[j];
}
if (j>(int)strlen(t))
return i-strlen(t)+1;
else
return 0;
}

void get_next(char *t,int *next)
{

int i=1,j=0;
next[0]=next[1]=0;
while (i<(int)strlen(t))
{
if (j==0||t[i]==t[j])
{
i++;
j++;
next[i]=j;
}
else j=next[j];
}

}

Answer 3

#define MaxStrLen 200
#include "graphics.h"
# include"stdio.h"
# include"stdlib.h"
# include"conio.h"
char s1[MaxStrLen],s2[MaxStrLen],s3[MaxStrLen],p[20];
int next[20];

void input();
int Index_KMP(char* s,char* t,int pos,int next[]);
void get_next(char* s,int next[]);
void output();
main()
{
input();
get_next(p,next);
output();
}

void input()
{
printf("please input the string of S1:\n");
gets(s1);
printf("please input the string of S2:\n");
gets(s2);
printf("please input the string of S3:\n");
gets(s3);
printf("please input the string of p:\n");
gets(p);

}

int Index_KMP(char* s,char* t,int pos,int next[])
{
int i,j,ls,lt;

i=pos-1,j=-1;
ls=strlen(s); lt=strlen(t);
while(i<ls && j<lt) {
if(j==-1 || s[i]==t[j]) {
i++; j++;
}
else {
j=next[j]-1;
}
}

if (j>=lt) return i-lt+1;
else return 0;

}

void get_next(char* s,int next[])
{
int i,j;
i=1; j=0;
next[0]=0;

while (i<strlen(s))
{
if (j==0 || s[i-1]==s[j-1])
{
i++; j++;
next[i-1]=j;
}
else
j=next[j-1];
}
printf("\nnext=");
for (i=0;i<strlen(p);i++)
printf("%d, ",next[i]);
}

void output()
{ printf("\n%d",Index_KMP(s1,p,0,next));
printf("\n%d",Index_KMP(s2,p,0,next));
printf("\n%d",Index_KMP(s3,p,0,next));
getch();
}

Answer 4

#include <stdio.h>
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 index_KMP(char str[], char pat[])
{
int i = 0;
int j = 0;
int next[255];
getNext(pat, next);
while (str[i])
{
if (pat[j] == '\0')
{
return (i - j);
}
if (str[i] == pat[j])
{
i++;
j++;
continue;
}
i += next[j+1]+1;
}
if (pat[j] == '\0')
{
return (i - j);
}
return -1;
}

int main()
{
char str_pattern[]="kaka";
char str_src[]="iamkaka";
printf("%d\n",index_KMP(str_src, str_pattern));
return 0;
}