Problem link :
Difficulty : Simple
Pre-requisites : Brute force, Big integers handling
Problem : Find the first position of occurrence of the string S in the infinite string D = 12345678910111213141… under an additional constraint.
Explanation
The additional constraint states that at least one integer should occur in S completely, so we can bruteforce this integer by bruteforcing its first and the last positions in S - let’s call them L and R. Then, we can check if the rest of the string matches.
It is fairly easy to check the fact of matching. First, we can check if the suffix of the string that corresponds to the substring [R+1…N] matches. This can be done by successively increasing the [L…R] substring and comparing the corresponding substrings. Pay attention that the length of the number may increase, so it isn’t correct to split the string into blocks of equal length. The [1…L-1] prefix can be checked in the same manner.
Let’s think of the final complexity of the solution: we spend O(N2) time to brute-force the left and the right positions of the integer that occurs completely. Then, we spend O(N) time to check that the number matches. So the final overall complexity is O(N3) which is perfectly OK for N <= 300.