串|数据结构

文章目录一、串的存储结构二、串的模式匹配算法BF算法（Brute-Force）KMP算法（Knuth、Morris、Pratt）一、串的存储结构//串的堆式顺序存储结构typedef struct{char *ch;int length;} HString;//串的链式存储结构#define CHUNKSIZE 80typedef struct{char[CHUN...

写代码的资资

266人浏览 · 2019-10-27 17:46:16

写代码的资资 · 2019-10-27 17:46:16 发布

文章目录

一、串的存储结构
二、串的模式匹配算法
- BF算法（Brute-Force）
- KMP算法（Knuth、Morris、Pratt）

一、串的存储结构

//串的堆式顺序存储结构
typedef struct 
{
	char *ch;
	int length;
} HString;

//串的链式存储结构
#define CHUNKSIZE 80
typedef struct
{
	char[CHUNKSIZE];
	struct Chunk *next;
}Chunk;

typedef struct
{
	Chunk *head;
	Chunk *tail;
	int length;
}LString;

二、串的模式匹配算法

BF算法（Brute-Force）

int Index_BF(SString S,SString T,int pos)
{
	int i = pos;
	int j = 1;
	while(i<= S.length && j <= T.length)
	{
		if(T[j]==S[i])
		{
			i++;
			j++;
		}
		else
		{
			i = i-j+2;
			j=1;
		}
	}
	if(j>T.length)
		return i-T.length;
	else
		return 0;
}

KMP算法（Knuth、Morris、Pratt）

void Get_next(SSting T,next[])
{
	int i=1;
	int j=0;
	next[i]=j;
	while(i<T.length)
	{
		if(T.ch[i]==T.ch[j] || j==0)
		{
			++i;
			++j;
			next[i]=j;
		}
		else
		{
			j=next[j];
		}
	}
}

int Index_KMP(SString S,SString T,int pos)
{
	i = pos;
	j=1;
	while(i<=S.length && j<=T.length)
	{
		if(S.ch[i] == T.ch[j]||j==0)
		{
			j++;
			i++;
		}
		else
			j = next[j];
	}
	if(j>T.length)
	{
		return i-T.length;
	}
	else
		return 0;
}