实验四 KMP算法

实验四 KMP算法,第1张

实验四 KMP算法

KMP算法查找字串位置
  • 实验内容
  • KMPStr.h
  • KMPStr.cpp
  • KMPStrPrj.cpp
  • 实验示例


实验内容

(1)对于给定的子串 T = ”abcaababa” ,求其next数组
(2)求子串 T 在主串 S 中第 pos 字符之后的位置


KMPStr.h
typedef struct
{
	char *ch;
	int len;
}HeapString;

void StrInitialize(HeapString *s); //初始化

void StrAssign(HeapString *s,char t[]); //生成字符串

void StrPrint(HeapString *s); //输出字符串

int Index_KMP(HeapString *s, HeapString *t, int pos, int next[]);
//利用子窜T的next函数,求T在主串S中第pos个字符之后的位置的KMP算法
//若不存在,则函数值为0,其中T非空,1 <= pos <= S->len

void get_next(HeapString *t,int next[]);
//求字串T的next函数值,并存放入数组next

KMPStr.cpp
#include "malloc.h" //#include "stdlib.h"
#include "KMPStr.h"
#include "stdio.h"


void StrInitialize(HeapString *s)
{	
	s->ch = '';	
	s->len = 0;	
}

void StrAssign(HeapString *s,char t[])
{	
	int i;	
	int length=0;	
	for(i=0 ; t[i]!='' ; i++)		
		length++;	
	s->ch=(char *)malloc((length+1)*sizeof(char));	
	for(i=0 ; ich[i] = t[i];	
	s->len = length;	
}

void StrPrint(HeapString *s)
{	
	int i;	
	if(s->len==0)
		printf("The String is empty!!");
	else
		for(i=0 ; i < s->len ; i++)		
		printf("%c",s->ch[i]);	
	putchar(10);	
}

int Index_KMP(HeapString *s, HeapString *t, int pos, int next[])
{	
	int i=pos, j=1;	
	while(i <= s->len && j < t->len)		
	{		
		if(j==0 || s->ch[i] == t->ch[j])		//继续比较			
		{			
			i++;
			j++;
		}
		else								//若字符不匹配,i不回溯,只用j回溯			
			j = next[j];	
	}	
	if(j > t->len-1)		
		return i - t->len;	
	else		
		return 0;	
}

void get_next(HeapString *t,int next[])
{	
	int i=1, j=0;	
	next[1] = 0;	
	while(i < t->len)		
	{		
		if(j==0 || t->ch[i] == t->ch[j])			
		{
			i++;			
			j++;			
			next[i] = j;			
		}	
		else		
			j = next[j];					//若字符不相等,则j值回溯	
	}	
}


KMPStrPrj.cpp
#include "stdio.h"
#include "KMPStr.h"
#define MAX 20

void main()
{	
	HeapString S,T;
	StrInitialize(&S);
	StrInitialize(&T);
	StrAssign(&S,"abammkabcaababcaabbabcbabcbdabwdnmd");
	printf("主串S:n");
	StrPrint(&S);
	StrAssign(&T,"abcaabbabc");
	printf("子串T:n");
	StrPrint(&T);
	printf("字串T长度:%dn",T.len);

	int pos=8;
	int index;
	int next[MAX];

	get_next(&T,next);			//获得next[j]的值,j从1开始,而不是0
	printf("next[j]:n");
	for(int i=1 ; i 

实验示例

主串S:
abammkabcaababcaabbabcbabcbdabwdnmd
子串T:
abcaabbabc
字串T长度:10
next[j]:
0 1 1 1 1 2 2 1 2 3
子串T在主串S中8位置之后的下标为12位置
Hello
Press any key to continue


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/3971331.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表(0条)

保存