codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.