CRANGIRL - Editorial

cranium2014
editorial
medium-hard

#1

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* 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.