Practice on Toph
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
You'll be given an array A of N strings containing lowercase english letters only and Q queries. In each query, you have to find the length of the longest palindromic substring which appears in at least L strings and at most R strings. If there is no such palindromic substring, print 0.
A palindrome is a word which reads the same backward and forward, such as madam, abba etc.A substring is a string of character(s) that is contained in another string. For example, abc has 6 substrings: a, ab, abc, b, bc, c.
A palindromic substring is a substring which reads the same backward and forward. For example, taka has 4 unique palindromic substrings: t, a, k, aka.
There will be multiple testcases. The first line of the input will contain an integer T, the number of testcases. The first line of each case will contain two integers N and Q. Then each of the next N lines will contain a string, ith line will contain the string Ai. Then the folowing Q lines will contain two integers each L and R, as described in the statement.
1 ≤ T≤ 151 ≤ N ≤ 1051 ≤ Q ≤ 1051 ≤ L ≤ R ≤ N1 ≤ |Ai| ≤ 105Sum of length over all N strings per case will be ≤ 106
Subtask 1 (10 points):1 ≤ T≤ 15, 1 ≤ N ≤ 10, 1 ≤ Q ≤ 100, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 20Sum of length over all N strings per case will be ≤ 100
Subtask 2 (30 points):1 ≤ T≤ 15, 1 ≤ N ≤ 100, 1 ≤ Q ≤ 10000, 1 ≤ L ≤ R ≤ N, 1 ≤ |Ai| ≤ 4100Sum of length over all N strings per case will be ≤ 10000
Subtask 3 (60 points): Original constraints.
For each query, print 1 line, ith line is the answer to the ith query.
Input | Output |
---|---|
1 3 6 aaac aaabbbbbb abbaaa 1 1 1 2 1 3 2 2 2 3 3 3 | 6 6 6 2 3 3 |
Dataset is huge, use faster I/O methods.
70% Solution Ratio
alamkhanEarliest,
phuleethanhFastest, 0.5s
hredhayxzLightest, 37 MB
UthsobShortest, 1944B
Login to submit