Given a string S and Q queries. Each query contains two integers M and P. The task is to find count number of strings of length M that occur exactly P times as substrings in S.

In the on-campus test, the constraints were S.length()<=10^3, so I wrote a code, preprocessing each substring using a map in O(N^2) and answered each query in O(1) and it passed.

Does it have some more optimal approach of O(N) or O(N*logN) if S.length()<=10^5 ?

Since it was on-campus drive, I don’t have a link to the problem statement.