PA 2010 Task Fragments: String Matching in Ranges of Integers

Revision en1, by minimario, 2018-01-12 19:50:13

Hi all,

I've recently come across this http://main.edu.pl/en/archive/pa/2010/fra. The problem statement is as follow: given up to n = 5000 disjoint intervals of the form [ai, bi], we let S be all the integers in these intervals (a1, a1 + 1, ..., b1, a2, ..., b2, .., bn Now, we have up to q = 500000 queries of strings, count the total number of times a string s will appear in the numbers of set S.

The only thing I can solve is if n = 1 or something, and I barely can see a way to approach this problem, especially since we can't iterate through all the intervals for each query.

If somebody could help, that would be great!

Best,

minimario

Tags strings, pa, polish, civil war

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English minimario 2018-01-12 19:50:13 734 Initial revision (published)