光谷网站建设公司,大数据精准营销获客系统,濮阳网站建设公司,图片模板免费下载题意#xff1a;给定两个序列a ,b, 如果在a中存在一段连续的序列使得 a[i]-b[0]k, a[i1]-b[1]k.... a[in-1]-b[n-1]k 就说b串在a串中出现过#xff01;最后输出b串在a串中出现几次#xff01; 思路#xff1a; KMP变形#xff01;如何转换成KMP求解呢#xff1f; 举一个例… 题意给定两个序列a ,b, 如果在a中存在一段连续的序列使得 a[i]-b[0]k, a[i1]-b[1]k.... a[in-1]-b[n-1]k 就说b串在a串中出现过最后输出b串在a串中出现几次 思路 KMP变形如何转换成KMP求解呢 举一个例子说明一下 a: 5 10 8 10 11 9 11 12 10 15 b: 4 2 4 5 3 根据题意 a中的 10 8 10 11 9 与 b是匹配的 11 9 11 12 10跟b也是匹配的 如何将b串以及 10 8 10 11 9 以及 11 9 11 12 10转换成同一个串这样好套用kmp啊 因为对应的数值的差值都是相同的 令a[i]-a[i1], b[i]-b[i1]! 这样也就是将串的长度减少了1这样就可以套kmp模板了 别忘记对特殊情况考虑一下 1 #includeiostream2 #includecmath 3 #includecstdio4 #includealgorithm5 #includecstring6 #define N 2000057 using namespace std;8 9 int f[N], a[N], b[N];
10 int n, w;
11 void getFail(){
12 f[0]0; f[1]0;
13 for(int i1; iw; i){
14 int jf[i];
15 while(j b[i] ! b[j]) jf[j];
16 if(b[i] b[j]) f[i1] j1;
17 else f[i1] 0;
18 }
19 }
20
21 void findText(){
22 int j0;
23 int cnt 0;
24 for(int i0; in; i){
25 while(j a[i] ! b[j]) jf[j];
26 if(a[i] b[j]) j;
27 if( j w ) cnt;
28 }
29 printf(%d\n, cnt);
30 }
31
32 int main(){
33 scanf(%d%d, n, w);
34 for(int i0; in; i){
35 scanf(%d, a[i]);
36 if(i) a[i-1] - a[i];
37 }
38
39 for(int i0; iw; i){
40 scanf(%d, b[i]);
41 if(i) b[i-1] - b[i];
42 }
43 if(n1 w1){
44 printf(%d\n, 1);
45 return 0;
46 }
47 else if(n1){
48 printf(%d\n, 0);
49 return 0;
50 }
51 else if( w1 ){
52 printf(%d\n, n);
53 return 0;
54 }
55 --n;
56 --w;
57 b[w] -1e6;
58 getFail();
59 findText();
60 return 0;
61 } View Code 转载于:https://www.cnblogs.com/hujunzheng/p/3997196.html
