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

Revision en3, by MissTolochin, 2020-02-27 11:26:06

Today I tried to solve this problem (https://codeforces.me/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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English MissTolochin 2020-02-27 11:26:06 297
ru3 Russian MissTolochin 2020-02-27 11:25:18 333
en2 English MissTolochin 2020-02-26 20:27:02 205
ru2 Russian MissTolochin 2020-02-26 20:26:00 170
en1 English MissTolochin 2020-02-26 20:22:04 890 Initial revision for English translation
ru1 Russian MissTolochin 2020-02-26 20:21:02 897 Первая редакция (опубликовано)