Concepts: Z algorithm, String matching
LEVEL: medium-hard
Problem Link:http://www.codechef.com/CRNM2014/problems/CRANGIRL
We can use the Z algorithm to solve this problem in O(|A|) time by running it on the string B#A, which is the concatenation of strings B and A with a character in between which doesn’t occur in both B and A.
The algorithm produces an array of Z values in which Z[i] is the longest common prefix length of substring (i, N+M) and complete string B#A. We can process this array in reverse direction to print longest running multiples ending at each value.