Поиск пароля

@Fixer_84 · Регистрация: 30.04.2016

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

Здравствуйте! Решил несложную задачу на строки, но в двух последних строках - ошибка выполнения. Помогите, пожалуйста, разобраться что не так в моей программе. Прошу не писать новый код, а помочь внести поправки в существующий.

Условие задачи:

Поиск пароля

Возможность отправлять закодированные сообщения во время Второй мировой войны была достаточно важной для союзников. Сообщения всегда отправлялись после их кодирования при помощи известного пароля. Иметь фиксированный пароль было небезопасно, поэтому возникла необходимость часто изменять его. Однако следовало разработать механизм отправления нового пароля. У одного из математиков, работавших в криптографической команде, возникла умная идея - отправить пароль, скрытый в самом сообщении. Интересным моментом было то, что получателю сообщения достаточно было знать только размер пароля, а потом найти его в полученном тексте.

Пароль размера n можно найти поиском в тексте наиболее часто встречаемой подстроки из n символов. После нахождения пароля все подстроки совпадающие с ним, удаляются из текста. Теперь пароль можно использовать для расшифровки сообщения.

Однако Ваша задача будет упрощена. Вам достаточно написать программу, которая по заданному размеру пароля и закодированному сообщению найдет пароль в соответствии с описанным выше алгоритмом.

Рассмотрим пример, в котором размер пароля равен трем (n = 3), а текст сообщения имеет вид baababacb. Паролем будет aba, потому что размер этой подстроки 3, она появляется чаще всего во всем тексте (дважды), а остальные шесть различных подстрок появляются только один раз (baa, aab, bab, bac, acb).

Входные данные:

Состоит из нескольких тестов. Каждый тест представляет собой одну строку, в которой находится длина пароля n (0 < n ≤ 10) и закодированное сообщение. Сообщение содержит только прописные буквы латинского алфавита, его длина не более 10^6 и не меньше n.

Выходные данные:

Для каждого теста в отдельной строке следует вывести искомый пароль. Если существует несколько паролей, удовлетворяющих задаче, то вывести лексикографически наименьший.

Входные данные:
3 baababacb

Выходные данные:
aba

Мое решение:

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
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, end, x, y, k, max, pos;
    string str, s;
    string T[100000];
    while (getline(fin, str))
    {
        pos = str.find(' ');
        N = atoi(str.substr(0, pos).c_str());
        str = str.substr(pos + 1);
        end = N;
        end--;
        k = 0;
        for (int i = 0; i < str.size() - end; i++)
        {
            T[k++] = str.substr(i, N); //Заносим подстроки заданной длины в массив
        }
        sort(T, T + k); //Сортируем массив (для получения лексиграфически меньшего пароля)
        x = y = max = 0;
        for (int i = y; i < k; i++) //Пробегаем по массиву подстрок
        {
            if (T[i+1] == T[i])
            {
                x++;
            }
            else
            {
                y = x; //Запоминаем очередную длину цепочки повторяющихся подстрок
                x++;
                if (x > max)
                {
                    max = x; //Находим максимальное число повторов (после сортировки)
                    s = T[i]; //Находим пароль максимальной длины (лексиграфически меньший)
                }
                x = 0;
            }
        }
        fout << s << endl; //Выводим искомый пароль
    }
    fin.close();
    fout.close();
    system("pause");
    return 0;
}

Добавлено через 11 минут
Тему можно закрывать. Я ошибся с размером массива. Он должен быть на порядок выше. (10^6 - как сказано в условии). Это будет максимум для для подстроки длиной 1 из одинаковых символов.

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ