串定义、KMP算法

本文主要是介绍串定义、KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

串的顺序存储

#include "datastr.h"
#define MAXLEN 255
typedef struct {
	char ch[MAXLEN+1];
	int length;
}SString;

堆式顺序存储

typedef struct {
	char* ch;
	int length;
}HString;

链式存储

#define CHUNKSIZE 80
typedef struct Chunk {
	char ch[CHUNKSIZE];
	struct Chunk* next;
}Chunk;

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

KMP算法

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

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

这篇关于串定义、KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！