PID442 / 数列匹配
题目描述

下面介绍一种新的匹配规则。

对于两个相互匹配的数列,其必须满足以下几个要求:

(1) 两个数列的长度相等。

(2) 两个数列中的第i大的数字的所在位置相同(若两个数字的大小相同,那么认为靠前的数字较小)。

例如,数列{1,3,1}和{4,8,5}相互匹配,

数列{1,4,9}和{5,4,7}不匹配。

现在给定一个长度为N的数列{A1,A2,…,An}和一个长度为M的模板数列{B1,B2,…,Bm}

求数列A中与模板数列B相匹配的子序列的个数(子序列可以部分重叠)。

数据规模

对于30%数据 N <= 1000 , M <= 30 ;

对于100%数据 N<=10000 , M <= 100 。

输入格式

第一行两个整数N,M

第二行N个整数,表示数列A

第三行M个整数,表示模板数列B

输出格式

一个整数,表示数列A中与模板数列B相匹配的子序列的个数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论