Nearly Shortest Repeating Substring

题面翻译

给你一个长度为 $n$ 的字符串 $s$ ，它由小写字母组成。求最短字符串 $k$ 的长度，使得多个（可能是一个） $k$ 可以连接在一起，形成一个长度与 $s$ 相同的字符串，且最多只有一个不同的字符。

更正式地说，求最短字符串 $k$ 的长度，使得 $c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$ 为某个正整数 $x$ ，字符串 $s$ 和 $c$ 的长度相同，且 $c_i \neq s_i$ 中最多有一个 $i$ （即存在 $0$ 或 $1$ 这样的位置）。

题目描述

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.

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

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^3 $ ) — the number of test cases.

The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 2\cdot10^5 $ ) — the length of string $ s $ .

The second line of each test case contains the string $ s $ , consisting of lowercase Latin characters.

The sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, print the length of the shortest string $ k $ satisfying the constraints in the statement.

样例 #1

样例输入 #1

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

样例输出 #1

1
4
13
2
10

提示

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.

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

可以被长度为l的k组成长度和s长度len相同，那么l必定是len的约数，所有先求约数，在所有约数中从小到大试，比如约数是a，每隔a个字符就把他加到map中，还有两个条件，map的元素个数个数一定是小于或等于两个才能保证只有最多一处不同导致的两个字符串不同，并且字符串个数最小是1，才能保证不同于其他字符串的字符只有一个

const int N = 2e5 + 10;
int a[N];
int b[N];
void solve()
{
    int n;
    cin >> n;
    int nn = n;
    string s;
    cin >> s;
    int h = 0;
    for (int i = 1; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            b[++h] = i;
            if (i != n / i) b[++h] = n / i;
        }
    }
    sort(b + 1, b + 1 + h);
    for (int i = 1; i <= h; i++)
    {
        map<string, int> p;
        for (int j = 0; j < nn; j+=b[i])
        {
            string os = s.substr(j, b[i]);
            p[os]++;
        }
        if (p.size() == 1)
        {
            cout << b[i] << '\n';
            break;
        }
        if (p.size() == 2)
        {
            string fw[3];
            int sh = 0;
            int mi = 1e9;
            for (auto q : p)
            {
                fw[++sh] = q.first;
                mi = min(mi, q.second);
            }
            if (mi == 1)
            {
                int ans = 0;
                for (int i = 0; i < fw[1].length(); i++)
                {
                    if (fw[1][i] != fw[2][i]) ans++;
                }
                if (ans <= 1)
                {
                    cout << b[i] << '\n';
                    break;
                }
            }

        }
    }

}