Hi everyone,

I was thinking about the following string problem:

You are given a string of length n, and q queries. Each query is a substring of the original string (s[l ... r]). For each query, you want to find the number of prefixes of the substring that are equal to a suffix. For example:

abcabc

2

1 3

1 5

For the first query, the answer should be 1, and the second query, the answer should be 2 (abcab == abcab, and ab == ab).

I haven't made much progress so far (I tried getting aho-corasick and suffix array to work, but I didn't find a way). Assuming $$$n \le 10^5$$$ and $$$q \le 10^5$$$, none of my ideas work.

Is there a solution to this problem, or is the lower bound on the time complexity $$$O(n^2+q)$$$ or $$$O(nq)$$$ (the best solutions i have found so far).

Excuse me if there are any mistakes here, as this is my first blog ever