Решить на С++ не слишком сложно

Question

Решить на С++ не слишком сложно

Festik Festikovich Ученик (97), на голосовании 1 неделю назад

Вам дана строка s
длиной n
, состоящая из строчных латинских символов. Найдите длину самой короткой строки k
, такой что несколько (возможно одна) копий k
могут быть сконкатенированы вместе, чтобы образовать строку той же длины, что и s
, и при этом имеется не более одного отличающегося символа.

Формально, найдите длину самой короткой строки k
, такой что c=k+⋯+kx раз
для некоторого положительного целого x
, строки s
и c
имеют одинаковую длину и ci≠si
для не более чем одного i
(т.е. существует 0
или 1
такая позиция).

Входные данные
Первая строка содержит одно целое число t
(1≤t≤103
) — количество тестов.

Первая строка каждого теста содержит одно целое число n
(1≤n≤2⋅105
) — длина строки s
.

Вторая строка каждого теста содержит строку s
, состоящую из строчных латинских символов.

Сумма n
по всем тестам не превышает 2⋅105
.

Выходные данные
Для каждого теста выведите длину самой короткой строки k
, удовлетворяющей условиям в условии.

Пример
Входные данныеСкопировать
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame
Выходные данныеСкопировать
1
4
13
2
10
Примечание
В первом примере вы можете выбрать k=a
и k+k+k+k=aaaa
, которая отличается от s
только во второй позиции.

Во втором примере вы не можете выбрать k
длиной один или два. Мы можем взять k=abba
, которая равна s
.

Answer 1

 #include <iostream>  
#include <string>  
 
using namespace std;  
 
int findShortestK(const string& s) {  
    int n = s.length();  
    for (int k = 1; k <= n; ++k) {  
        if (n % k == 0) {  
            int diff = 0;  
            for (int i = 0; i < n; ++i) {  
                if (s[i] != s[i % k]) { 
                    ++diff; 
                    if (diff > 1) break; 
                } 
            }  
            if (diff <= 1) return k;  
        }  
    }  
    return n;  
}  
 
int main() {  
    int t;  
    cout << "Введите количество тестов: ";  
    cin >> t;  
     
    for (int i = 1; i <= t; ++i) {  
        string s;  
        cout << "Тест " << i << ". Введите строку: ";  
        cin >> s;  
        cout << "Результат: " << findShortestK(s) << "\n\n";  
    }  
}

На попробуй ещё раз