解题思路:KMP算法就是掌握next数组的实现过程
附视频教程:
https://www.bilibili.com/video/av2975983/?p=39
注意事项:
next[]数组和T数组,下标1为第一个元素
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void get_next(char T[],int *next)
{
int i,j;
i=0;//前缀
j=1;//后缀
next[1]=0;
while(j<next[0]) {
if(i==0 || T[i]==T[j])
{
i++;
j++;
next[j]=i;
}
else
{
i=next[i];
}
}
}
int main (){
char T[1000];
scanf("%s",T);
int *next=(int*)malloc(sizeof(int)*(strlen(T)+1));//为next数组开辟长度
next[0]=strlen(T);//数组长度储存在next[0]中
for(int i=strlen(T);i>0;i--)//数组后移
{
T[i]=T[i-1];
}
get_next(T,next);
for(int i=1;i<=next[0];i++){
printf("%d ",next[i]);
}
}
0.0分
0 人评分
C二级辅导-分段函数 (C语言代码)浏览:558 |
A+B for Input-Output Practice (III) (C语言代码)浏览:569 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:505 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:574 |
三角形 (C++代码)记忆化搜索浏览:1220 |
三角形 (C++代码)递归(存在大量重复计算,容易出现时间超限)浏览:774 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:520 |
1118(求助_已解决)浏览:329 |
矩阵的对角线之和 (C语言代码)浏览:1344 |
小O的图案 (C语言代码)浏览:912 |