You can get every substring in a list with ; <@<\\. s
If k is quite large, your approach with every k </ s could work like this:
subs=: [:; (-.~&i.&>: #) <@<\ ]
tab=: (<:@# ; }: ; {:)&>
count=: ~. ,. <@#/.~
f=: count@:tab@:subs
4 f s
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
