字符串_KMP

void get_next (String 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];
	}
}

对于一个字符串,从第二个开始寻找他的最大相同前后缀,实现代码为以上部分,对于连续的前后缀只需要next[i-1]+1便可以获得当前字符的next序列,如果当前字符在期望的相同前后缀中找不到对应的字符(即T[I]!=T[j])则返回j=next[j-1],再对T[j]与T[I]进行判断,向前寻找是否存在一个相同前后缀;

int Index_KMP (String S, String T, int next[]){    //S为长串,T为短串
	int i = 1, 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;
}

从主串的头开始进行判断,当副串的的字符与主串的字符不对应时,找到副串该字符位置对应的next表,副串对应主串的位置跳跃next表对应的单位字符,再次从跳跃位置开始继续对应,反复上述操作,直到找到主串中能够与副串完全匹配的字符串的位置

全部评论

相关推荐

代码部分:#include int&nbsp;main(){&nbsp;&nbsp;&nbsp;&nbsp;char&nbsp;line[150];&nbsp;//&nbsp;定义一个字符数组line,用于存储输入的字符串,最大长度为149个字符加上一个空字符'\0'。&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i,&nbsp;j;&nbsp;//&nbsp;定义循环计数器i和j。&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;输入一个字符串:&nbsp;&quot;);&nbsp;//&nbsp;提示用户输入字符串。&nbsp;&nbsp;&nbsp;&nbsp;fgets(line,&nbsp;(sizeof&nbsp;line&nbsp;/&nbsp;sizeof&nbsp;line[0]),&nbsp;stdin);&nbsp;//&nbsp;使用fgets函数从标准输入读取字符串,包括空格,最多读取149个字符。&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;遍历字符串,直到遇到空字符'\0'&nbsp;&nbsp;&nbsp;&nbsp;for(i&nbsp;=&nbsp;0;&nbsp;line[i]&nbsp;!=&nbsp;'\0';&nbsp;++i)&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;如果当前字符不是字母也不是空字符,则需要移除 while (!( (line[i] >=&nbsp;'a'&nbsp;&amp;&amp;&nbsp;line[i]&nbsp;=&nbsp;'A'&nbsp;&amp;&amp;&nbsp;line[i]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;从当前位置i开始,将所有字符向后移动一位,覆盖非字母字符&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j&nbsp;=&nbsp;i;&nbsp;line[j]&nbsp;!=&nbsp;'\0';&nbsp;++j)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line[j]&nbsp;=&nbsp;line[j+1];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//&nbsp;将字符串末尾的空字符'\0'向前移动一位&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line[j]&nbsp;=&nbsp;'\0';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;输出:&nbsp;&quot;);&nbsp;//&nbsp;提示将显示处理后的字符串。&nbsp;&nbsp;&nbsp;&nbsp;puts(line);&nbsp;//&nbsp;输出处理后的字符串。&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;&nbsp;//&nbsp;程序结束,返回0表示成功。}知识点总结:1.&nbsp;**字符数组和字符串**:使用字符数组来存储字符串,并了解字符串以空字符'\0'结束。2.&nbsp;**输入输出函数**:使用`printf`和`fgets`函数进行输出和输入操作,使用`puts`函数输出字符串。3.&nbsp;**循环控制**:使用`for`循环遍历字符串中的每个字符。4.&nbsp;**条件判断**:使用`while`循环和条件判断来检查字符是否为字母或空字符。5.&nbsp;**数组操作**:通过数组索引操作来移动和覆盖数组中的字符。难点:1.&nbsp;**字符串处理**:理解如何通过遍历和条件判断来处理字符串中的字符。2.&nbsp;**数组操作**:理解如何在数组中移动字符来覆盖非字母字符。3.&nbsp;**边界条件处理**:确保在覆盖非字母字符时正确处理字符串的结尾。这段代码的难点在于理解如何通过循环和条件判断来处理字符串中的字符,以及如何在数组中移动字符来覆盖非字母字符。代码本身逻辑简单,但需要对基本的编程概念有一定的理解
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务