JARVIS and LCP
All submissions for this problem are available.JARVIS(Just A Rather Very Intelligent System) has still many things to learn to become more intelligent. Tony Stark wants to teach Competitive Programming to it. So he starts directly with Strings and tells JARVIS about Longest Common Prefix(LCP) of two strings. Also Tony gives JARVIS a set of strings S1, S2, ..., Sn. JARVIS starts playing with those strings and comes up with a problem. The problem is as follows,
If LCP of Xth and Yth strings is L then how many times L occures in the set as a substring of any string?
JARVIS comes with many such X's and Y's to Pepper. Being very busy, she asks you to tell the answers of the JARVIS' quesions. Can you help her answering the questions?
InputThe first line contains N, the number of strings in the set.
The Next N lines contain the strings of the given set.
The next line contains Q, the number of questions.
Each line of the next Q lines contains Xi and Yi, the indexes(1-based) of the two strings of ith question.
OutputFor each question, output on a separate line the answer of the question.
- 1 ≤ N ≤ 105
- 1 ≤ Length of Si ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ Xi ≤ Yi ≤ N
- Sum of lengths of all strings ≤ 5*105
- Strings contain only lower case letters.
ExplanationFor query 1, LCP L is aba that occures 2 times in ababa, once in aba.
For query 3, LCP L is an empty string so the answer is 0.
|Tags||insomnia, suffix-array, vikky_codder|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.