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

By applying suffix automaton, O(len(s) + k^2) complexity is received.