Sukarna_Paul's blog

By Sukarna_Paul, history, 12 months ago, In English,

Problem Link How can I approach for this problem???

F. Find the Substrings

Score: 1

CPU: 3s Memory: 1500MB

You are given a string S and Q queries. On the ith query, you will be given two integers Ni and Mi. Now for each query, you have to find such strings consisting of lowercase letters whose lengths are at least Ni and at most Mi and also those strings are not substrings of S.

For example: You are given S=“abac”. If a query contains Ni=3 and Mi=4 then according to our problem, “aba”, “bac” and “abac” are not valid as they are substrings of S while “abc” is a valid string as it is not substring of S and also maintaining the constraints for the length. Now you have to find all other strings which are also valid for this string S.

To make the problem a bit simple, you don’t have to print all the strings. You will just need to print the number of such strings which are valid. To make the output more simple, print the answer modulo 1000000007 (109+7 ).

Input The first line of the input file will be a single integer T (1 ≤ T ≤ 5), denoting the number of test cases.

Each test case contains two lines. First line will contain the string S (1 ≤ |S| ≤ 1000000) of lowercase letters and the second line will contain an integer Q (1 ≤ Q ≤ 100000). Each of the next Q lines will contain two integers Ni and Mi (1 ≤ Ni ≤ Mi ≤ |S|).

Output For each test case, the first line of the output should contain the case number in the format: “Case X:”, where X is the test case number. Each of the next Q lines should contain the answer for the specific query modulo 1000000007 (109+7).

Sample Input 1 abcab 5 1 2 2 2 3 5 1 1 1 5 Output Case 1: 696 673 12355922 23 12356618

N.B. Data set is large. Use faster I/O methods.

  • Vote: I like it
  • 0
  • Vote: I do not like it

12 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • Suffix Automation for counting the unique substring lengths
  • Fenwik Tree as a container for the counting
  • so answer is $$$26^{N_i} + \dots + 26^{M_i} - (FT(M_i) - FT(N_i-1))$$$