第五届蓝桥杯决赛B组C/C++——信号匹配

标题:信号匹配

从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]

思路:KMP,没搞懂,等搞懂了思路一定补上

#include <bits/stdc++.h>
using namespace std; 
// 生成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
			j=next[j];  //填空位置
         
        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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注 Java 基础分享

详解 Java NIO

文件的抽象化表示,字节流以及字符流的文件操作等属于传统 IO 的相关内容,我们已经在前面的文章进行了较为深刻的学习了。

600
来自专栏MySQL

深入理解JAVA中的NIO

传统的 IO 流还是有很多缺陷的,尤其它的阻塞性加上磁盘读写本来就慢,会导致 CPU 使用效率大大降低。

1395
来自专栏CDA数据分析师

超能教程 十分钟学会 Python!

假设你希望学习Python这门语言,却苦于找不到一个简短而全面的入门教程。那么本教程将花费十分钟的时间带你走入Python的大门。本文的内容介于教程(Totur...

1886
来自专栏Web 开发

JavaScript的对象引用

在一个函数体内,var变量声明的变量,其作用域只在该函数体内,对于函数体外而言,是不可见的(废话)。

670
来自专栏java思维导图

值得收藏!Redis五大数据类型应用场景(一)

Redis开创了一种新的数据存储思路,使用Redis,我们不用在面对功能单调的数据库时,把精力放在如何把大象放进冰箱这样的问题上,而是利用Redis灵活多变的数...

1274
来自专栏何俊林

Android性能提升之强引用、软引用、弱引用、虚引用使用

背景:收到公众投稿,《从面试题中看Java的Reference(引用)》,总感觉少了实际的例子和应用场景。于是结合自己工作中场景,小小补充下。小总结一下。看下A...

22910
来自专栏企鹅号快讯

verilog编程要素整理时刻牢记

verilog编程建议 1、不使用初始化语句; 2、不使用延时语句; 3、不使用循环次数不确定的语句,如:forever,while等; 4、尽量采用同步方式设...

1778
来自专栏LEo的网络日志

go常见错误总结

2575
来自专栏MongoDB

MongoDB基础概念与事务支持

MongoDB4.0新增了对事务的支持,本文首先介绍一些MongoDB的基础概念,后文会对4.0新增的事务功能进行解读

37020
来自专栏开发与安全

从零开始学C++之boost库(一):详解 boost 库智能指针(scoped_ptr<T> 、shared_ptr<T> 、weak_ptr<T> 源码分析)

一、boost 智能指针 智能指针是利用RAII(Resource Acquisition Is Initialization:资源获取即初始化)来管理资源。关...

2240

扫码关注云+社区