nguyenquocthao00's blog

Query strings suffix comparison
By nguyenquocthao00, history, 7 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nguyenquocthao00 (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

→ Reply