Ошибка передачи сообщения

@RafaProfa · Регистрация: 22.11.2015

Студворк — интернет-сервис помощи студентам

В Берляндском государственном университете локальная сеть между серверами не всегда работает без ошибок. При передаче двух одинаковых сообщений подряд возможна ошибка, в результате которой эти два сообщения сливаются в одно. При таком слиянии конец первого сообщения совмещается с началом второго. Конечно, совмещение может происходить только по одинаковым символам. Длина совмещения должна быть положительным числом, меньшим длины текста сообщения.

Например, при передаче двух сообщений «abrakadabra» подряд возможно, что оно будет передано с ошибкой описанного вида, и тогда будет получено сообщение вида «abrakadabrabrakadabra» или «abrakadabrakadabra» (в первом случае совмещение произошло по одному символу, а во втором — по четырем).

По полученному сообщению t определите, возможно ли, что это результат ошибки описанного вида работы локальной сети, и если возможно, определите возможное значение s.

Не следует считать ошибкой ситуацию полного наложения друга на друга двух сообщений. К примеру, если получено сообщение «abcd», следует считать, что в нём ошибки нет. Аналогично, простое дописывание одного сообщения вслед за другим не является признаком ошибки. Например, если получено сообщение «abcabc», следует считать, что в нём ошибки нет.

Входные данные
В единственной строке выходных данных следует непустая строка t, состоящая из строчных букв латинского алфавита. Длина строки t не превосходит 100 символов.

Выходные данные
Если сообщение t не может содержать ошибки, выведите «NO» (без кавычек) в единственную строку выходных данных.

В противном случае в первой строке выведите «YES» (без кавычек), а в следующей строке выведите строку s — возможное сообщение, которое могло привести к ошибке. Если возможных ответов несколько, разрешается вывести любой из них.

Примеры

входные данные
abrakadabrabrakadabra
выходные данные
YES
abrakadabra

входные данные
acacacaca
выходные данные
YES
acaca

входные данные
abcabc
выходные данные
NO

входные данные
abababab
выходные данные
YES
ababab

входные данные
tatbt
выходные данные
NO

Примечание
Во втором примере подходящим ответом также является строка acacaca.
С чего начинать подскажите пожалуйста.

@кот Бегемот · 09.01.2017, 11:09

RafaProfa, это несложная задача. К сожалению, я не знаю С++, но на Паскале я её сделал минут за 10. Расскажу алгоритм и приведу решение на Паскале, если надо, кто-нибудь обязательно переведёт на С++.
Итак:
1. Находим длину строки t и целочисленным делением её середину k (если длина нечётна, увеличиваем k на 1).
2. Проходим по строке t в обратном направлении от точки k до 2 символа.
3. Выделяем из строки t подстроку, включающую все символы от взятой точки до конца
4. Проверяем, есть ли в строке t выделенная подстрока и начинается ли эта подстрока с 1 символа.
5. Печатаем подстроку и YES, выходим из цикла, или доходим до конца и печатаем NO

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var
c,s,t:string;
b,k,i,f:integer;
begin
readln(t);
b:=length(t);
if b mod 2=0 then k:=b div 2 else
k:=b div 2+1;
for i:=k downto 2 do
begin
c:=copy(t,i,b-i+1);
if pos(c,t)=1 then begin
writeln('yes');
f:=1;
writeln(c);
break;
end;
end;
if f=0 then writeln('no');
end.

@doctypehtml · 25.10.2019, 12:07

Вот программа на c++, не понял как работает код на Паскале выше, но могу объяснить свой.
например даётся строка "abdacaa", она чётная, поэтому сравниваются два string "bda" равно "caa" ( "abdacaa"), нет. Поэтому теперь сравниваются "ac" "aa" ("abdacaa"), опять не равны. Теперь сравниваются "a" "a" ("abdacaa"), они равны выводится "YES" и первый string (который был введён) минус "a", то есть "abdaca".

P.S. программа все претесты прошла))

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <string>
 
using namespace std;
int main() {
    string arr;
    int n=0,lengh,site;
    cin>> arr;
    n=arr.length();
    string left, right;
    if (n%2==1) {
        lengh=n/2;
        site=1;
        left=arr.substr(1, n/2);
        right=arr.substr(n/2+1);
            while (lengh>0) {
            
        if (left==right) {
            cout << "YES" << endl;
            arr=arr.substr(0,n-lengh);
            cout << arr;
            break;
        }
        lengh-=1;
        site+=2;
        left=arr.substr(site, lengh);
        right=arr.substr(site+lengh);
            }
        if (lengh==0) {
            cout << "NO";
        }
        
    } else {
        lengh=n/2-1;
        site=2;
        left=arr.substr(2, lengh);
        right=arr.substr(lengh+2);
        while (lengh>0) {
            
            if (left==right) {
            cout << "YES" << endl;
            arr=arr.substr(0,n-lengh);
            cout << arr;
            break;
        }
        lengh-=1;
        site+=2;
        left=arr.substr(site, lengh);
        right=arr.substr(site+lengh);       
        }
        if (lengh==0) {
            cout << "NO";
        }
    }
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .
Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .

@RafaProfa 3 / 3 / 1 Регистрация: 22.11.2015 Сообщений: 59

	Ошибка передачи сообщения 17.11.2016, 11:22. Показов 4997. Ответов 2 Метки нет (Все метки) В Берляндском государственном университете локальная сеть между серверами не всегда работает без ошибок. При передаче двух одинаковых сообщений подряд возможна ошибка, в результате которой эти два сообщения сливаются в одно. При таком слиянии конец первого сообщения совмещается с началом второго. Конечно, совмещение может происходить только по одинаковым символам. Длина совмещения должна быть положительным числом, меньшим длины текста сообщения. Например, при передаче двух сообщений «abrakadabra» подряд возможно, что оно будет передано с ошибкой описанного вида, и тогда будет получено сообщение вида «abrakadabrabrakadabra» или «abrakadabrakadabra» (в первом случае совмещение произошло по одному символу, а во втором — по четырем). По полученному сообщению t определите, возможно ли, что это результат ошибки описанного вида работы локальной сети, и если возможно, определите возможное значение s. Не следует считать ошибкой ситуацию полного наложения друга на друга двух сообщений. К примеру, если получено сообщение «abcd», следует считать, что в нём ошибки нет. Аналогично, простое дописывание одного сообщения вслед за другим не является признаком ошибки. Например, если получено сообщение «abcabc», следует считать, что в нём ошибки нет. Входные данные В единственной строке выходных данных следует непустая строка t, состоящая из строчных букв латинского алфавита. Длина строки t не превосходит 100 символов. Выходные данные Если сообщение t не может содержать ошибки, выведите «NO» (без кавычек) в единственную строку выходных данных. В противном случае в первой строке выведите «YES» (без кавычек), а в следующей строке выведите строку s — возможное сообщение, которое могло привести к ошибке. Если возможных ответов несколько, разрешается вывести любой из них. Примеры входные данные abrakadabrabrakadabra выходные данные YES abrakadabra входные данные acacacaca выходные данные YES acaca входные данные abcabc выходные данные NO входные данные abababab выходные данные YES ababab входные данные tatbt выходные данные NO Примечание Во втором примере подходящим ответом также является строка acacaca. С чего начинать подскажите пожалуйста. 0