TLE '16 Contest 7 P6 - Everyone Hates Reading

View as PDF

Submit solution


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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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.

Constraints

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
ab
abc
a 1 3
abcerhfgdryrtjfhdgshdj 2 3
aaaaaaaaa 1 3

Sample Output

3
2
1

Comments


  • 3
    zxyl  commented on May 15, 2018, 12:01 p.m.

    Are all root words guaranteed to be distinct?