### nguyenquocthao00's blog

By nguyenquocthao00, history, 3 weeks ago,

Given 2 strings s1 and s2, and a list of queries. Each query has 2 values: i,j; for each query you need to check if s1[i:] >= s2[j:].
For example:
s1 = "abababaa"
s2 = "abababab"
Query 0,0 => false
Query 0,2 => true
Query 2,0 => false
How to do this efficiently?

 » 3 weeks ago, # |   +11 Construct a suffix array for s1+s2, and use the values you get from each iteration of the suffix array just like a sparse table
•  » » 3 weeks ago, # ^ |   0 Can you explain more? Why build suffix array for s1+s2, and how to use it to check
•  » » » 3 weeks ago, # ^ |   +3
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by nguyenquocthao00 (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 2 →   +8 Notice that the lexicographical comparison is basically comparing on the first position where they differ. This means that you can binary search with hashing to find the first position where they differ, and compare the elements.
 » 3 weeks ago, # | ← Rev. 2 →   +16 Hash the two strings using polynomial hashing.Now if you want to compare $s1[l..r]$ and $s1[l'..r']$ this can be done in O(1). To ensure correctness you can use double hashing.If you want the first point of difference you can do a binary search else for comparison you have an O(1) solution.