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
↵
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
