Question

期末作业急求!!!用C语言编写函数计算字符串中子串出现的次数。

编写函数计算字符串中子串出现的次数，如“abcdefabcdefabcdef”中出现子串“cde”三次（不允许使用标准库函数子串查找功能）。主函数实现输入字符串、输出字符串以及调用计算子串出现次数函数步骤。要求数据结构定义，急求各位大神谢谢！！！

Answer 1

#include <stdio.h>
#include <string.h>
#define MAX 1000
int next[MAX];
int s_len;
char str[MAX], str_t[MAX];

void get_next(){
	int i;
	next[0] = -1;
	for(i = 1; i < s_len; ++i){

		int j = next[i-1];
		while(str_t[i] != str_t[j+1] && j != -1)	
			j = next[j];
		if(str_t[i] == str_t[j+1])
			next[i] = j + 1;
		else
			next[i] = -1;

	}
}

int kmp(char *str, char *str_t){

	int i;
	int len = strlen(str);
	int j;
	int cnt = 0;
	s_len = strlen(str_t);
	get_next();
	j = -1;
	for(i = 0; i < len; ++i){

		if(str[i] != str_t[j+1] && j != -1)
			j = next[j];
		if(str[i] == str_t[j+1]){
			++j;
		}
		if(j == s_len-1){
			cnt++;
			j = next[j];
		}
	}
	return cnt;
}



int main(){

	scanf("%s %s", str, str_t);

	printf("cnt %d\n", kmp(str, str_t));
	return 0;
}

输入 abcdefabcdefabcdef cde

追问

可以帮忙谢谢数据结构定义吗 谢谢！！！

追答

什么意思。。。。。