第五届蓝桥杯决赛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 条评论
登录 后参与评论

相关文章

来自专栏mathor

C++STL中vector使用策略(二)

1284
来自专栏大数据风控

Python中如何进行数据分组

数据分组 根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间进行研究,以揭示其内在联系和规律性。 cut 函数: cut(series,...

2977
来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

3916
来自专栏前端说吧

JS-用js的for循环实现九九乘法表以及其他算数题等

3816
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

37212
来自专栏数据结构与算法

深海中的STL—nth_element

如果让你求区间第k大,你会怎么做呢? 主席树?确实是个不错的选择(不过像我这种垃圾还是乖乖打暴力吧) 在c++的stl库中,提供了nth_element...

3637
来自专栏TensorFlow从0到N

讨厌算法的程序员 1 - 插入排序

什么是算法 在说插入排序之前,我们了解下《算法导论》对算法的从两种不同角度的定义。 一般性解释: 算法是定义良好的计算过程,它取一个或一组值作为输入,并产生...

3344
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3415
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3615
来自专栏我是攻城师

使用位运算替代模运算

3235

扫码关注云+社区