Interesting String Problem

Revision en8, by Apple_Method, 2021-04-09 20:22:01

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Apple_Method 2021-04-09 21:18:49 184
en8 English Apple_Method 2021-04-09 20:22:01 17 (published)
en7 English Apple_Method 2021-04-09 20:21:50 17 Tiny change: 'd getting aho-corasick and suffix ar' -> 'd getting suffix ar'
en6 English Apple_Method 2021-04-09 20:20:55 0 Tiny change: '\nabcabc\n2\n1 3\n1 5\n\nF' -> '\nabcabc\n\n2\n\n1 3\n\n1 5\n\nF'
en5 English Apple_Method 2021-04-09 20:20:11 6 Tiny change: '\nabcabc\n2\n1 3\n1 5\n\nF' -> '\nabcabc\n\n2\n\n1 3\n\n1 5\n\nF' (saved to drafts)
en4 English Apple_Method 2021-04-09 20:19:38 0 (published)
en3 English Apple_Method 2021-04-09 20:19:16 1
en2 English Apple_Method 2021-04-09 20:18:30 17 Tiny change: ' blog ever' -> ' blog ever.'
en1 English Apple_Method 2021-04-09 20:17:19 901 Initial revision (saved to drafts)