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.

Codeforces Round #282 Div. 1 - Obsessive String

Problem Statement:
494B - Obsessive String

Solution:
I like this problem, and for me it is a particularly challenging one. Thankfully the editorial for this round is very well-written and detailed. I learnt quite a lot from this problem.

Firstly we need to find an efficient way to mark all occurrence of t in s, and here we can employ the \(O(N)\) Knuth-Morris-Pratt string matching algorithm. We keep track of all indexes i of s such that s[i-|t|+1 .. i] matches t exactly in an array g[i], setting such indexes g[i] as 1, and 0 otherwise. The hardest part is to come up with the right DP state. Here, the one that will work is: let f[i] be the number of ways to choose the substrings from [1..i], such that the last (right-most) substring ends with index i.