Discussion @ 1941. Scary Martian Word @ Timus Online Judge

What is optimal asymptotic?

Posted by Vladimir Plyashkun [CSU] 4 Jul 2013 23:06

What is optimal asymptotic for this problem? My algo has O(M*log(N)) where N - length of scary Martian word, and M - length of text of Ovchinnikov's book, but i have TLE on 21th test

Re: What is optimal asymptotic?

Posted by Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 5 Jul 2013 00:10

O(M + N) is optimal. But maybe you can succed with your asymptotic if use fast I/O

Discussion of Problem 1941. Scary Martian Word