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

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