Task about finding a substring in a string using a suffix array

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Today I tried to solve this problem (https://codeforces.net/gym/102069/problem/J).

There are two strings s, t. Given q queries. Each request must be answered how many times the string s[l1..r1] lies on the segment t[l2..r2] (l1, r1,l2, r2 we read in each request).

It seems to be obvious that in this case, you can use a suffix array, and then use the bin.search for all the necessary sub-sections (and for O (the length of the string to be found), check whether this sub-section is suitable), then use the segment tree to calculate the answer. However, this takes place in the first two subgroups (takes 25 points). There is one problem, it is that there is no guarantee that the sum of all the substrings that we have to check will not exceed any constant (for example, the length of the string). This means that you need to optimize the binary search (that is, find the desired sub-sections for a constant less than O(the length of the string to be found)). What data structure can be used to do this?

P.S: I was able to optimize my solution (in binary search, you can do a check using another binary search, checking whether this sub-section is suitable, using hashes). But it still takes only 60 points (passes only if the length of string does not exceed 100,000). What else can be optimized?

Comments (7)

Show archived | Write comment?

staniewzki

5 years ago, # |

If you preprocess the lcp array on the suffix array, you can get lcp of two suffixes in O(1) as it is just RMQ, which can be achieved with sparse table. Now you have lcp of any two substrings in O(1), so comparing any two substrings lexicographicly is also in O(1), what leads to binsearch in just O(logn), not including the length of substring in the complexity.

More details

→ Reply

Kavaliro

← Rev. 5 →

I solved it with a different approach.

Concatenate the two string with a diameter in between (S $ T) and build both suffix array and LCP array. Now for each query, find the range in the suffix array which contain the the substring from S, this can be done with binary search and sparse table.

After you find such range for each query, the answer for that query is the number of indices in its range that have values between [L, R-len+1], where L and R are represent the range from T for that query, and len is the length of the substring we're counting.

To count those values, you can either build a segment tree with each node being a sorted vector, and do a binary search on it ( O(n*log^2(n) + m*log^2(n), probably won't get 100 score), or you can process the queries offline. the answer for some query with corresponding range [a, b] in the suffix array, is :

Ans = (Number of values >= L in [a,b]) + (Number of values <= R-len+1 in [a,b]) — ( Length of [a,b] )

So, you can update values from 0 to |S|+|T| in order and find the (Number of values >= L), and similarly for the (Number of values <= R-len+1)

My Submission

P.S: I'm using an O(n) suffix array algorithm, and its code is just unreadable XD.