Repeated string 2 - MarisaOJ: Marisa Online Judge

Given a string

$S$ and

$q$ queries of the form

$l,r$ , find the length of the shortest string that, when repeated some number of times, exactly forms the substring

$S[l...r]$ . ### Input - The first line contains the string

$S$ . - The second line contains an integer

$q$ . - The next

$q$ lines each contain two integers

$l$ and

$r$ . ### Output - Print

$q$ integers, each being the answer to the corresponding query. ### Constraints -

$1 \le |S| \le 5 \times 10^5$ . -

$1 \le q \le 10^6$ . ### Example Input:

$8 aaabcabc 3 1 3 3 8 4 8$

Output:

$1 3 5$

Explanation: - Query 1: Repeating the string

$a$ three times results in the string

$aaa$ . - Query 2: Repeating the string

$abc$ two times results in the string

$abcabc$ . - Query 3: Repeating the string

$abcab$ one time results in the string

$abcab$ .

Topic

Hashing

Rating

1900

Source

POI

Solution (0)

Solution