编程题
信号匹配 ### 题目描述 **本题为代码补全填空题,请将题目中给出的源代码补全,并复制到右侧代码框中,选择对应的编译语言(C/Java)后进行提交。若题目中给出的源代码语言不唯一,则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉,填上你的答案。提交后若未能通过,除考虑填空部分出错外,还需注意是否因在复制后有改动非填空部分产生错误。** 从X星球接收了一个数字信号序列。 现有一个已知的样板序列。需要在信号序列中查找它首次出现的位置。这类似于串的匹配操作。 如果信号序列较长,样板序列中重复数字较多,就应当注意比较的策略了。可以仿照串的 KMP 算法,进行无回溯的匹配。这种匹配方法的关键是构造 $next$ 数组。 $next[i]$ 表示第 $i$ 项比较失配时,样板序列向右滑动,需要重新比较的项的序号。如果为 -1,表示母序列可以进入失配位置的下一个位置进行新的比较。 下面的代码实现了这个功能,请仔细阅读源码,推断划线位置缺失的代码。 ### 源代码 **C** ```c #include #include int* make_next(int pa[], int pn) { int* next = (int*)malloc(sizeof(int)*pn); next[0] = -1; int j = 0; int k = -1; while(j < pn-1){ if(k==-1 || pa[j]==pa[k]){ j++; k++; next[j] = k; } else k = next[k]; } return next; } int find(int da[], int an, int pa[], int pn) { int rst = -1; int* next = make_next(pa, pn); int i=0; int j=0; int n = 0; while(i