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

相关文章

来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏一个会写诗的程序员的博客

java.sql.SQLException: connection holder is null

java.sql.SQLException: connection holder is null

1341
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9784
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

781
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2189
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1202
来自专栏我和未来有约会

silverlight beta 2 将在本周末发布.

太开心了,刚刚收到微软silverlight.net的邮件.  确定了 将在本周末发布beta2. 以下是部分邮件内容 引用: There are some...

1976
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2828
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1282

扫码关注云+社区