Question

Возможность отправлять закодированные сообщения во время Второй мировой войны была достаточно важной для союзников. Сообщения всегда отправлялись после их кодирования при помощи известного пароля. Иметь фиксированный пароль было небезопасно, поэтому возникла необходимость часто изменять его. Однако следовало разработать механизм отправления нового пароля. У одного из математиков, работавших в криптографической команде, возникла умная идея - отправить пароль, скрытый в самом сообщении. Интересным моментом было то, что получателю сообщения достаточно было знать только размер пароля, а потом найти его в полученном тексте. Пароль размера n можно найти поиском в тексте наиболее часто встречаемой подстроки из n символов. После нахождения пароля все подстроки совпадающие с ним, удаляются из текста. Теперь пароль можно использовать для расшифровки сообщения. Однако Ваша задача будет упрощена. Вам достаточно написать программу, которая по заданному размеру пароля и закодированному сообщению найдет пароль в соответствии с описанным выше алгоритмом. Рассмотрим пример, в котором размер пароля равен трем (n = 3), а текст сообщения имеет вид baababacb. Паролем будет aba, потому что размер этой подстроки 3, она появляется чаще всего во всем тексте (дважды), а остальные шесть различных подстрок появляются только один раз (baa, aab, bab, bac, acb).Технические условия Входные данные Состоит из нескольких тестов. Каждый тест представляет собой одну строку, в которой находится длина пароля n (0 < n ≤ 10) и закодированное сообщение. Сообщение содержит только прописные буквы латинского алфавита, его длина не более 106 и не меньше n. Выходные данные Для каждого теста в отдельной строке следует вывести искомый пароль. Если существует несколько паролей, удовлетворяющих задаче, то вывести лексикографически наименьший.

Answer 1

Type
    piece = record
        value: string[10];
        count := 1;
    end;

var
    pieces: array[1..200]of piece;
    i, j, n, pieces_n: integer;
    s, p: string;
    found: boolean;
    imax:=1;

begin
    read(s);
    read(n);
    for i := 1 to length(s) - n + 1 do
    begin
        p := Copy(s, i, n);
        found := false;
        for j := 1 to pieces_n do
            if pieces[j].value = p then begin
                pieces[j].count := pieces[j].count + 1;
                found := true;
                if pieces[imax].count < pieces[j].count then
                    imax := j;
                break;
            end;
        if not found then begin
            pieces_n := pieces_n + 1;
            pieces[pieces_n].value := p;
        end;
    end;
   
    writeln(pieces[imax].value);
end.

Answer 2

Introduction

During World War II, the ability to send encoded messages was crucial for the Allies. Messages were always sent after being encoded using a known password. However, having a fixed password was unsafe, so there was a need to frequently change it. One of the mathematicians working in the cryptographic team came up with a clever idea - to send the password hidden within the message itself. The interesting part was that the recipient only needed to know the size of the password and then find it in the received text. The password of size 'n' could be found by searching for the most frequently occurring substring of length 'n' in the text. Once the password was found, all matching substrings were removed from the text. Now the password could be used to decrypt the message.

Algorithm Description

The algorithm to find the password in the encoded message can be summarized as follows: 1. Determine the size of the password, denoted as 'n'. 2. Search for the most frequently occurring substring of length 'n' in the encoded message. 3. Remove all substrings that match the password from the encoded message. 4. The remaining text is the decrypted message.

Example

Let's consider an example where the size of the password is 3 (n = 3) and the encoded message is "baababacb". The password would be "aba" because it is the most frequently occurring substring of length 3 in the entire text (appearing twice), while the other six different substrings appear only once (baa, aab, bab, bac, acb).

Technical Specifications

- Input: The input consists of multiple tests. Each test is represented by a single line containing the length of the password 'n' (0 < n ≤ 10) and the encoded message. The message contains only uppercase Latin letters, with a length of no more than 106 and no less than 'n'. - Output: For each test, output the desired password on a separate line. If there are multiple passwords that satisfy the conditions, output the lexicographically smallest one.

Implementation

To solve this problem, you can use the following Python code:

def find_password(n, encoded_message):
    password = ""
    max_count = 0
    for i in range(len(encoded_message) - n + 1):
        substring = encoded_message[i:i+n]
        count = encoded_message.count(substring)
        if count > max_count:
            max_count = count
            password = substring
    return password

# Example usage
n = 3
encoded_message = "baababacb"
password = find_password(n, encoded_message)
print(password)

This code defines a function `find_password` that takes the length of the password 'n' and the encoded message as input. It iterates through all possible substrings of length 'n' in the encoded message, counts their occurrences, and keeps track of the substring with the maximum count. Finally, it returns the password. In the example usage, the function is called with the provided values, and the resulting password is printed.

Please note that this is a simplified implementation to demonstrate the algorithm. In a real-world scenario, additional considerations such as efficiency and error handling would need to be taken into account.