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