1950E.md (1703B)
1 Source: https://codeforces.com/problemset/problem/1950/E 2 3 E. Nearly Shortest Repeating Substring 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a string $s$ of length $n$ consisting of lowercase Latin characters. Find the length of the shortest string $k$ such that several (possibly one) copies of $k$ can be concatenated together to form a string with the same length as $s$ and, at most, one different character. 22 23 More formally, find the length of the shortest string $k$ such that $c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$ for some positive integer $x$, strings $s$ and $c$ has the same length and $c_i \neq s_i$ for at most one $i$ (i.e. there exist $0$ or $1$ such positions). 24 25 Input 26 27 The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. 28 29 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of string $s$. 30 31 The second line of each test case contains the string $s$, consisting of lowercase Latin characters. 32 33 The sum of $n$ over all test cases does not exceed $2\cdot10^5$. 34 35 Output 36 37 For each test case, print the length of the shortest string $k$ satisfying the constraints in the statement. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 4 47 48 abaa 49 50 4 51 52 abba 53 54 13 55 56 slavicgslavic 57 58 8 59 60 hshahaha 61 62 20 63 64 stormflamestornflame 65 ``` 66 67 Output 68 69 ``` 70 1 71 4 72 13 73 2 74 10 75 ``` 76 77 Note 78 79 In the first test case, you can select $k = \texttt{a}$ and $k+k+k+k = \texttt{aaaa}$, which only differs from $s$ in the second position. 80 81 In the second test case, you cannot select $k$ of length one or two. We can have $k = \texttt{abba}$, which is equal to $s$.