徐州建站公司哪家好,一键优化内存,WordPress修改模板,wordpress+谷歌加速美妙音乐 发布时间: 2017年7月3日 13:14 最后更新: 2017年7月5日 13:47 时间限制: 500ms 内存限制: 128M 描述 一段音乐是由若干个音符组成的#xff0c;音乐中的某段音符称为旋律。给定一首音乐#xff0c;问某个旋律出现了多少次。注意#xff1a; #xff08;1音乐中的某段音符称为旋律。给定一首音乐问某个旋律出现了多少次。注意 1音乐中旋律是可以升调或降调的例如 4 5 6和5 6 7是一个旋律 2旋律不能重叠。 输入 多组测试数据。 每组数据第一行有两个正整数n,m。 第二行有n个整数表示这段音乐。 第三行有m个整数表示一段旋律。 输入数据满足音乐和旋律中的音符均为1到88之间的整数即对应钢琴里的88种音调。 n,m不超过5×105。 总输入量∑n∑m≤106。 输出 对于每组数据输出一行一个整数表示答案。 样例输入1 复制 14 3
1 1 5 5 6 6 5 4 4 3 3 2 2 1
2 2 1 样例输出1 3 题解
对题目中给出的m个音符组成的的旋律做差分得到序列为(m-1)个相邻差组成记为模式
然后对整段音乐做差分得到(n-1)个音符组成的序列记为主串
对主串用模式进行KMP匹配得到的匹配数目即是答案。
~注意啦题目中的旋律不能够重叠也就是说如果成功匹配到一个模式的时候那么紧接着的下一个位置的差也不能用了所以要i;j 0;
代码: #include iostream
#include cstdio
using namespace std;
#define MAXN 2000001
int n,m;
int a[MAXN];
int b[MAXN];
int s[MAXN];
int fail[MAXN];
void make_fail()
{for (int i 1, j 0; i m-1; i){while (j s[i] ! s[j])j fail[j - 1];if (s[i] s[j])fail[i] j;else fail[i] 0;}
}
int search(int *str)
{int ans 0;for (int i 0, j 0; i n-1; i){while (j str[i] ! s[j])j fail[j - 1];if (str[i] s[j] (j m-1)){ans;i;j 0;}}return ans;
}
int main(){while(~scanf(%d%d,n,m)){for(int i 0;i n;i){scanf(%d,a[i]);}for(int i 0;i m;i){scanf(%d,b[i]);}if(m 1){printf(%d\n,n);continue;}for(int i 0;i n-1;i){a[i] a[i1] - a[i];}for(int i 0;i m-1;i){s[i] b[i1] - b[i];}make_fail();int ans search(a);printf(%d\n,ans);}return 0;
}
