首页 > 代码库 > codeforces MUH and Cube Walls
codeforces MUH and Cube Walls
题意：给定两个序列a ,b, 如果在a中存在一段连续的序列使得
a[i]-b[0]==k, a[i+1]-b[1]==k.... a[i+n-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[i+1], b[i]-=b[i+1]!
这样也就是将串的长度减少了1，这样就可以套kmp模板了！
别忘记对特殊情况考虑一下！
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 #define N 200005 7 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 i=1; i<w; ++i){14 int j=f[i];15 while(j && b[i] != b[j]) j=f[j];16 if(b[i] == b[j]) f[i+1] = j+1;17 else f[i+1] = 0;18 }19 }20 21 void findText(){22 int j=0;23 int cnt = 0;24 for(int i=0; i<n; ++i){25 while(j && a[i] != b[j]) j=f[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 i=0; i<n; ++i){35 scanf("%d", &a[i]);36 if(i) a[i-1] -= a[i];37 }38 39 for(int i=0; i<w; ++i){40 scanf("%d", &b[i]);41 if(i) b[i-1] -= b[i];42 }43 if(n==1 && w==1){44 printf("%d\n", 1);45 return 0;46 }47 else if(n==1){48 printf("%d\n", 0);49 return 0;50 }51 else if( w==1 ){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 }
codeforces MUH and Cube Walls
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。