## Saturday, December 20, 2014

### Codeforces Round 269 Div. 2 Problem D - MUH and Cube Walls

Problem Statement:
471D - MUH and Cube Walls

Solution:
And interesting string matching problem since it does not so obviously look like one. For the $$a_i$$ and $$b_i$$ given, store $$s_i$$ and $$p_i$$ as follows: $$s_i = a_i - a_{i-1}$$ and $$p_i = b_i - b_{i-1}$$, which are basically array of differences. Then the problem reduces to finding occurrences of p in s, which can be done efficiently in $$O(N)$$ using KMP algorithm. Don't forget about one special case where b has only one element.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int s[200005], p[200005];
int par[200005];

int main(){
int n, m, u;
scanf("%d%d", &n,&m);
for(int i=0;i<n;++i){
if(i==0) scanf("%d", &s[i]);
else {
scanf("%d", &u);
s[i-1] = u - s[i-1];
s[i] = u;
}
}
for(int j=0;j<m;++j){
if(j==0) scanf("%d", &p[j]);
else {
scanf("%d", &u);
p[j-1] = u - p[j-1];
p[j] = u;
}
}
n--; m--;
//special case: m == 0
if(m == 0) {
printf("%d\n", n+1);
return 0;
}
//otherwise:
par[0] = -1;
int k = -1;
for(int i=1;i<m;++i){
while(k != -1 && p[k+1] != p[i]) {
k = par[k];
}
if(p[k+1] == p[i]) {
++k;
}
par[i] = k;
}
k = -1;
int cnt = 0;
for(int i=0;i<n;++i){
while(k != -1 && p[k+1] != s[i]){
k = par[k];
}
if(p[k+1] == s[i]){
++k;
}
if(k == m-1) ++cnt;
}
printf("%d\n", cnt);
return 0;
}