串

串的模式匹配算法

#include <stdio.h>
#include <stdlib.h>
// 串的长度
#define MAXLEN 255

// 函数结果状态代码
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
// infeasible 不可执行的
#define INFEASIBLE -1
// overflow 溢出的
#define OVEREFLOW -2

// Status 函数类型，用来表示函数结果状态代码
typedef int Status;

// 顺序串的结构定义
typedef struct {
	// 存储串的一维数组
	char ch[MAXLEN + 1];
	// 串的当前长度
	int length;
}SString;

// 串的模式匹配算法(BF算法)
// 默认从第一个字符开始匹配
int index_BF(SString S, SString T) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length) {
		// 匹配成功，主串和子串依次向下匹配
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		// 匹配失败，主串返回开始匹配的位置的下一个位置，子串返回初始位置
		else {
			i = i - j + 2; // i = i - ( j - 1 ) + 1;
			j = 1;
		}
	}
	// 子串全部匹配成功，返回子串在主串中的位置
	if (j > T.length) return (i - T.length);
	// 主串的全部子串都未被匹配上，返回0；
	return 0;
}
// 形参传开始匹配位置 pos>=1
int index_BF(SString S, SString T, int pos) {
	int i = pos, j = 1;
	while (i <= S.length && j <= T.length) {
		// 匹配成功，主串和子串依次向下匹配
		if (S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		// 匹配失败，主串返回开始匹配的位置的下一个位置，子串返回初始位置
		else {
			i = i - j + 2; // i = i - ( j - 1 ) + 1;
			j = 1;
		}
	}
	// 子串全部匹配成功，返回子串在主串中的位置
	if (j > T.length) return (i - T.length);
	// 主串的全部子串都未被匹配上，返回0；
	return 0;
}

// 计算next数组（很难理解）
void get_Next(SString T, int next[]) {
	int i = 1, j = 0;
	next[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else {
			j = next[j];
		}
	}
}

// 计算nextval数组
void get_Nextval(SString T, int nextval[]) {
	int i = 1, j = 0;
	nextval[1] = 0;
	while (i < T.length) {
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++;
			j++;
			if(T.ch[i] != T.ch[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
		}
		else {
			j = nextval[j];
		}
	}
}

// 串的模式匹配算法（KMP算法）pos>=1 (采用nextval数组时调用get_Nextval方法即可)
int index_KMP(SString S, SString T, int pos) {
	int i = pos, j = 1;
	int* next;
	get_Next(T, next);
	while (i <= S.length && j <= T.length) {
		// 匹配成功，主串和子串依次向下匹配
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++;
			j++;
		}
		// 匹配失败，子串返回next数组中对应的值的位置
		else {
			j = next[j];
		}
	}
	// 子串全部匹配成功，返回子串在主串中的位置
	if (j > T.length) return (i - T.length);
	// 主串的全部子串都未被匹配上，返回0；
	return 0;
}



int main() {
	return 0;
}