Блог пользователя nguyenquocthao00

Query strings suffix comparison
Автор nguyenquocthao00, история, 7 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится +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

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 месяцев назад, # |
← 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.

→ Ответить
»
7 месяцев назад, # |
← 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.

→ Ответить