SubstringQueries | Topcoder Archive

Problem Statement

You are given a String S and a int k. Generate the string T by concatenating k copies of S. E.g., if S = "abc" and k = 2, then T = "abcabc".

Consider the following type of query: We are given a positive integer integer X not exceeding the length of T. Consider all (contiguous) substrings of T that have length exactly X. Let Q(X) be the 0-based index in T where the lexicographically smallest among all these strings starts. In case of a tie, Q(X) is the smallest such index.

Let A be the sum of all Q(X), where X goes from 1 to the length of T. Return A modulo 10^18.

Definition

Class:: SubstringQueries
Method:: solve
Parameters:: String, int
Returns:: long
Method signature:: long solve(String S, int k)
(be sure your method is public)

Constraints

S will contain between 1 and 2,500 characters, inclusive.
Each character in S will be a lowercase English letter ('a'-'z').
k will be between 1 and 10^9, inclusive.

Examples

```
"aaaaaaaaa"
```
```
1
```
```
Returns: 0
```
In case of a tie, Q(X) is always the smallest possible value: in this case, zero.
```
"zaba"
```
```
2
```
```
Returns: 7
```
T = "zabazaba". All of Q(1) through Q(7) are equal to 1. For example, the lexicographically smallest substring of length 4 is "abaz", starting at index 1, so Q(4) = 1. Q(8) is 0.
```
"acaa"
```
```
2
```
```
Returns: 10
```
Q = {0, 2, 2, 2, 2, 2, 0, 0}
```
"aa"
```
```
4
```
```
Returns: 0
```
This is exactly the same T as in Example 0.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.