TLE '16 Contest 7 P6 - Everyone Hates Reading

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 256M

Problem types

Your brain after reading certain books.

Your neighbourhood fox has another English project. There's only one problem ... it involves reading. Foxen Everyone hates reading and will do anything to avoid it.

Your neighbourhood fox is given a long article of text, containing N words. He is then given M root words which he must research, and a range [l, r] in the text to use. Of the words from l to r, please help him count the number of words that either has the root word as a prefix or is a prefix of the root word.


N \le 100\,000

M \le 100\,000

The total length of all words in the article of text and the root words will each be no greater than 100\,000.

Input Specification

2 integers, N and M.

N lines, each with a string of lowercase English letters.

M lines, each with a string of lowercase English letters and 2 integers l and r.

Output Specification

N lines, each with an integer: the answer to each of the queries.

Sample Input

3 3
a 1 3
abcerhfgdryrtjfhdgshdj 2 3
aaaaaaaaa 1 3

Sample Output



  • 2
    liwi  commented on May 15, 2018, 12:01 p.m.

    Are all root words guaranteed to be distinct?