DTMA2015 RSTRING - EDITORIAL

PROBLEM LINK:

Author: Arpit Aggarwal ( arpitdec5 )

Tester: Arpit Aggarwal ( arpitdec5 )

Editorialist: Arpit Aggarwal ( arpitdec5 )

DIFFICULTY:

MEDIUM

PREREQUISITES:

Z algorithm ( a string algorithm )

PROBLEM:

In this problem a string is given where the " w " string is the longest substring which is also its prefix. We are asked to remove some characters from the starting so that the remaining string would have " w " as a substring and also as its prefix.

QUICK EXPLANATION:

The problem is a direct application of Z algorithm although use of KMP is also possible here .
We just have to find the Z array and then find the maximum value in it . If the maximum value occurs more than 1 time its possible otherwise not .

EXPLANATION:

Lets see what the problem is asking for :
Initially assume we have a string " abcabcdabc ". Now for finding the " w " string we can go naive way by comparing each element with the first but that will take O ( n^ 2 ) time . This is where we use Z algorithm .

Defination of Z algorithm :
Given a string S the Z algorithm computes a z array where the ith element denotes the longest substring starting from the ith position matching with the prefix of the given string .
So for the given string " abcabcdabc " the z array would look something like this
z array - 0 0 0 3 0 0 0 3 0 0
For more info on how to code this algorithm either refer to my code or look this link :
http://codeforces.com/blog/entry/3107

Now we have the z array . After this the problem is nothing as it just asks to find whether the max value in the given z array occurs more than one time and if does print YES with the number characters to be removed which is the first position at which the max value occurs in z array otherwise the answer is NO .

AUTHOR’S SOLUTIONS: