【C语言数据结构】字符串

• TOP0、BF算法
• 一、KMP算法
• 二、图解与分析

#include 
#include 
#include 

typedef struct {
	char *ch;
	int len;
}SString;

int MAXSIZE = 10;
int bf(SString s, SString t); 

int bf(SString s, SString t) {
	int i = 1, j = 1;
	while ( i <= s.len && j <= t.len) {
		if (s.ch[i] == t.ch[j]) {	
			i ++;
			j ++;
		} else {
			i = i - j + 2;
			j = 1;
		}
	}
	if ( j > t.len ) return i - t.len;
	return 0; 
}

int main() {
	SString s, t;
	s.ch = (char *)malloc(MAXSIZE * sizeof(char));
	s.ch ++;
	t.ch = (char *)malloc(MAXSIZE * sizeof(char));
	t.ch ++;
	printf("请输入一个主串：");
	scanf("%s", s.ch);
	s.len = strlen(s.ch);
	printf("请输入一个子串：");
	scanf("%s", t.ch);
	t.len = strlen(t.ch);
	s.ch --;
	t.ch --;
	int result;
	result = bf(s, t);
	printf("%dn", result);
	
	free(s.ch);
	free(t.ch);
	return 0;
}

#include 
#include 
#include 

typedef struct {
	char *ch;
	int len;
}SString;

int MAXSIZE = 10;
void next(SString t, int next[]);
int Index_KMP(SString s, SString t, int next[]); 

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

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

int main() {
	SString s, t;
	s.ch = (char *)malloc(MAXSIZE * sizeof(char));
	s.ch ++;
	t.ch = (char *)malloc(MAXSIZE * sizeof(char));
	t.ch ++;
	printf("请输入一个主串：");
	scanf("%s", s.ch);
	s.len = strlen(s.ch);
	printf("请输入一个子串：");
	scanf("%s", t.ch);
	t.len = strlen(t.ch);
	s.ch --;
	t.ch --;
	// 求next 
	int next[t.len + 1];
	get_next(t, next);
	// KMP算法
	int result;
	result = Index_KMP(s, t, next);
	printf("%d ", result); 
	free(s.ch);
	free(t.ch);
	return 0;
}