CF2164H PalindromePalindrome

We define the humor value of a string $ t $ as the length of the longest palindrome string which occurs at least twice in it. Formally, a string $ p $ is humor with respect to $ t $ , if and only if both of the following conditions are met: 1. $ p $ is a palindrome, and 2. there exist at least two different indices $ i \in [1, |t| - |p| + 1] $ , such that $ t[i, i + |p| - 1] = p $ . The humor value of $ t $ is defined as the maximum length among all humor strings with respect to $ t $ . You are given a string $ s $ of length $ n $ which only contains lowercase Latin letters and $ q $ queries. Each query contains two integers $ l_i $ , $ r_i $ , and you need to find the humor value of the string $ s[l_i, r_i] $ . Here, $ a[l, r] $ is defined as the string $ a_l,a_{l+1},\ldots,a_r $ .

The first line contains two integers $ n $ , $ q $ ( $ 1\le n,q\le 5\cdot10^5 $ ). The second line contains a string $ s $ . The next $ q $ lines contain the description of queries. The $ i $ -th line contains two integers $ l_i $ , $ r_i $ ( $ 1\le l_i\le r_i\le n $ ).

On the $ i $ -th line, output the answer to the $ i $ -th query.

In the first query, the following palindrome strings occur at least twice: a,aa,aaa,aaaa,b,bb,bbb. The longest one is aaaa, so the humor value is $ 4 $ . In the second query, one of the longest humor strings with respect to $ s[2, 7] $ is aa.