实验四 KMP算法

实验四 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