I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.
By dividing the submission into $$$ \gt \sqrt{n}$$$ and $$$\le\sqrt{n}$$$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.
Could anyone help me optimize the constant factor further, or is KMP unable to pass?
My KMP passed by memoising it 260210442
I'm taking a look
OK. To recover from this I went to learn Aho-Corasick Automaton this evening and it went out pretty funny, 25/26 test cases passed on the template.
https://mirror.codeforces.com/contest/1968/submission/301727963 I have also encountered the same problem. Can you help me see why this kmp cannot pass this question. I think the complexity of KMP is correct.
https://mirror.codeforces.com/problemset/submission/1968/303781322 Hello my friend, just now I was inspired and discovered a very effective optimization method that can reduce the time from 3.2s to 0.6s. My friend, you can notice that many prefixes of length i are repeatedly calculated many times during the binary kmp process. We can optimize these repetitions by using a memory array. The optimized efficiency is as high as 80%, which is astonishing! The code I have modified will be marked with//#############################################################