Problem 2590 --Lyndon Substring

2590: Lyndon Substring

正确率: $0.00\%$ 下一题

Description

A string

w is said to be a Lyndon word if

w is lexicographically smaller than any of its cyclic rotations.
The longest Lyndon substring of a string

s is the longest substring of

s which is a Lyndon word.
Chiaki has

n strings

s1,s2,…,sn. She has some queries: for some pair

(i,j), find the length of the longest Lyndon substring of string

sisj.

There are multiple test cases. The first line of input contains an integer

T, indicating the number of test cases. For each test case:
The first line contains two integers

n and

(1≤n,m≤105) -- the number of strings and the number of queries.
Each of the next

n lines contains a nonempty string

(1≤si≤105) consisting of lowercase English letters.
Each of the next

m lines contains two integers

i and

j (

1≤i,j≤n) denoting a query.
It is guaranteed that in one test case the sum of all

|s| does not exceed

5×105 and that in all cases the sum of all

|s| does not exceed

5×106.
It is guaranteed that neither the sum of all

n nor the sum of all

m exceeds

106.

For each query, output an integer denoting the answer.

1
2 1
aa
bb
1 2

竞赛编号	竞赛名称	竞赛时间	访问比赛