发布时间: 2017年7月3日 13:14 最后更新: 2017年7月5日 13:47 时间限制: 500ms 内存限制: 128M
描述一段音乐是由若干个音符组成的，音乐中的某段音符称为旋律。给定一首音乐，问某个旋律出现了多少次。注意：
（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[i+1] - a[i]; } for(int i = 0;i < m-1;i++){ s[i] = b[i+1] - b[i]; } make_fail(); int ans = search(a); printf("%d\n",ans); } return 0; }
