从X星球接收了一个数字信号序列。
现有一个已知的样板序列。需要在信号序列中查找它首次出现的位置。这类似于串的匹配操作。
如果信号序列较长,样板序列中重复数字较多,就应当注意比较的策略了。可以仿照串的KMP算法,进行无回溯的匹配。这种匹配方法的关键是构造next数组。
next[i] 表示第i项比较失配时,样板序列向右滑动,需要重新比较的项的序号。如果为-1,表示母序列可以进入失配位置的下一个位置进行新的比较。
下面的代码实现了这个功能,请仔细阅读源码,推断划线位置缺失的代码。
// 生成next数组
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;
}
// da中搜索pa, da的长度为an, pa的长度为pn
int find(int da[], int an, int pa[], int pn)
{
int rst = -1;
int* next = make_next(pa, pn);
int i=0; // da中的指针
int j=0; // pa中的指针
int n = 0;
while(i<an){
n++;
if(da[i]==pa[j] || j==-1){
i++;
j++;
}
else
__________________________; //填空位置
if(j==pn) {
rst = i-pn;
break;
}
}
free(next);
return rst;
}
int main()
{
int da[] = {1,2,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,2,1,2,1,1,2,1,1,2,1,1,1,2,1,2,3};
int pa[] = {1,2,1,1,2,1,1,1,2};
int n = find(da, sizeof(da)/sizeof(int), pa, sizeof(pa)/sizeof(int));
printf("%d\n", n);
return 0;
}
注意:通过浏览器提交答案。只填写缺少的内容,不要填写任何多余的内容(例如:说明性文字或已有符号)
j = next[j]
java实现第五届蓝桥杯信号匹配
JAVA 实现 蓝桥 匹配 信号 第五届
2023-09-14 08:58:10 时间
信号匹配
相关文章
- java oracle数据备份_Java实现Oracle数据库备份
- Java队列实现
- 第一个Java项目———Java实现简单图书管理系统(GUI)
- java 随机数算法_Java随机数算法原理与实现方法实例详解
- Java入门代码_java编程自学网
- Java cloneable_java浅克隆和深克隆
- Java实现 图片水印或者文字水印详解编程语言
- 初识Java NIO详解编程语言
- 实现Java程序操作MySQL数据库(java调用mysql)
- Java操作MySQL数据库:实现看似不可能的梦想(java连接mysql数据库)
- 实现Linux上的Java环境:从安装到配置(linux安装java环境)
- java实现Excel数据导出详解编程语言
- Java监控MySQL性能:实现数据库运行优化(java监控mysql)
- Java实现Redis事务管理(redis事务java)
- Java轻松使用Redis实现数据高效存储(java使用redis)
- 键处理 Java处理Redis过期键的实现方式(redisjava过期)
- 时间解决Java操作Redis实现自动过期时间(redisjava过期)
- Java操作Redis管理实现可靠过期策略(redisjava过期)
- 实现Redis中 Java实现的过期缓存策略(redisjava过期)
- 策略Java中Redis的过期策略实现(redisjava过期)
- 策略Java中采用Redis过期策略的实现(redisjava过期)
- 性能Java操作Redis实现高性能过期缓存(redisjava过期)
- 处理Java实现Redis过期处理(redisjava过期)
- 时间利用Java实现Redis中键值对的超时管理(redisjava过期)
- Java编程实现MySQL表备份(java备份mysql表)
- 进程Linux下创建多个Java进程的简易方法(linux 多个java)
- Java编程实现MySQL数据库连接(java连mysql数据库)
- 在Linux上实现Java程序的运行(linux运行java程序)
- Java Redis一次实现无限数据加速的尝试(用java redis)
- 利用Redis锁实现Java程序并发控制(redis锁java实现)
- java二维数组矩阵乘法的实现方法
- Java基于高精度整型实现fibonacci数列的方法