ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2118. Cipher Message 4

What is difficulty of correct solution?
Posted by Zergatul 21 Mar 2021 08:15
I have O(len(s) * k^2), and it is definitely too slow (TL#26).

BTW, and here is some tests (don't want to create separate topic):

3
CC
00
1
01
*****
ans=-1

3
BAB
10
111
0
*****
ans=7

3
BA
00
01
1
*****
ans=3

3
CA
001
000
01
*****
ans=5
Re: What is difficulty of correct solution?
Posted by bsu.mmf.team 20 Jun 2021 23:24
By applying suffix automaton, O(len(s) + k^2) complexity is received.