Is it possible to solve this problem using suffix automata? I got TL5.
But I think that O(N * K) solution have to work faster. Am I wrong? Thanks.

PS. Got AC with KMP O(N * K).

Edited by author 26.08.2015 00:30

Just got AC with suffix automation.  0.95 sec,  1.5MegaBytes.
Nothing tricky,  just avoided STL.
Construct an automation for every window and find number of different  paths.
I think my program is pretty slow because when I am constructing an automation I am using modulo operation every step (before adding every new symbol)  to deal with cyclic shift.  Obviously it can be improved by checking whether i+k>len(s)  and branching.

Also my program is slow because I am allocating and deallocating an entire array for DAWG for every window.  Obviously it can be allocated once