Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
gogaby
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 28
#1

Нарушен предел памяти при тестах - C++

22.03.2013, 16:37. Просмотров 312. Ответов 0
Метки нет (Все метки)

Условие задания:
Текст шифруется с помощью ключа, представляющего собой слово небольшой длины из строчных латинских букв. В шифруемом тексте заменяются только латинские буквы, остальные символы остаются неизменными. Латинские буквы разделяются на блоки так, что длина всех блоков (кроме, может быть, последнего) равна длине ключа. Пусть a1 — номер первой буквы блока в латинском алфавите, b1 — номер первой буквы ключа. Тогда первая буква блока заменяется буквой, чей номер в алфавите равен a1 + b1 (если a1 + b1 > 26, то берется величина a1 + b1 − 26). При этом прописная буква заменяется на прописную, а строчная — на строчную. Вторая и последующие буквы блоков шифруются с помощью соответствующих букв ключа аналогичным образом.

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

Определите ключ литореи, имеющий минимальную длину, на основании имеющихся данных!

Входные данные
Первая строка текстового файла littera.in содержит величину N — количество символов в каждом фрагменте (1 ≤ N ≤ 106). Далее следует незашифрованный и зашифрованный фрагменты. Зашифрованный фрагмент начинается с новой строки, но каждый из фрагментов может быть разбит на несколько строк произвольным образом.
Выходные данные
Единственная строка выходного файла littera.out должна содержать искомый ключ. Если задача имеет несколько решений, выведите наименьшее из них в лексикографическом порядке.
ПРИМЕР:
littera.in
41
To be or not t
o be? What is the question!
Yp ru aw oej ft cu?
Mtfu yi fmf gkqxuyez!
littera.out
apple|


Собственно вот моя реализация, которая работает нормально, но при длине ключа около 65к символов программа-тестировщик выдает : "Нарушен предел памяти 500м 192.9 Mb". длина исходного текста при этом не известна.

Подскажите пожалуйста в чем проблема, и как её исправить? Поможет ли хранение ключа в файле вместо строки string?

Добавлено через 22 секунды
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <string>
 
using namespace std;
 
 
char subtraction(char &letter, char &addicted_letter)
{
    int key_number = addicted_letter - letter;
    if (key_number<=0)
        key_number = 26 + key_number;
    return key_number + 96;
}
bool is_letter(char &symbol)
{
    return ((symbol>=65 && symbol<=90)||(symbol>=97 && symbol<=122));
}
 
void main(){
    
    FILE *first_block;
    FILE *second_block;
    FILE *output;
    errno_t error;
    
    error = fopen_s (&first_block, "littera.in", "r");
    error = fopen_s (&second_block, "littera.in", "r");
    error = fopen_s (&output, "littera.out", "wr");
    char start_symbol;
    char end_symbol;
    char *digits = new char [256];
    fgets(digits,255,first_block);
    unsigned int n = atoi(digits);
    fgets(digits,255,second_block);
    delete []digits;
    unsigned long i;
    for (i=0; i<n;)
    {
        if ((end_symbol = fgetc(second_block))!= '\n')
            i++;
    }
    end_symbol = fgetc(second_block);
    char symbol;
    string temp;
 
    string key;
    unsigned long r=0,k=1,t=0, num=1;
    for (i=0; i<n;i++)
    {
        do 
            start_symbol = fgetc(first_block);
        while (start_symbol == '\n');
 
        do
            end_symbol = fgetc(second_block);
        while (end_symbol == '\n');
        if (is_letter(start_symbol))
        {
            symbol = subtraction(start_symbol,end_symbol);
            if (symbol == key[r])
            {
                r++;
                if (r == key.length())
                {
                    num++;
                    r=0;
                    temp = "";
                }
                else
                {
                    temp += symbol; 
                    
                }
            }
            else
            {
                for (unsigned long j=0; j<num; j++)
                    key = key + key;
                num=0;
                r=0;
                key = key + temp + symbol;
                temp="";
            }
        }
    }
    unsigned long len = (long)key.length();
    string tt;
    string minimal_key = key;
    for (i=0; i<len; i++)
    {
        temp = key;
        temp.resize(len-1);
        tt = key.at(len-1);
        key = tt + temp;
        if (minimal_key > key)
            minimal_key = key;
 
    }
    
    fputs(minimal_key.c_str(),output);
    
 
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2013, 16:37     Нарушен предел памяти при тестах
Посмотрите здесь:
Переполнение по времени на больших тестах C++
Задача на коробки, ошибка в проверочных тестах C++
C++ Ошибка памяти при выполнении, при компиляции не выводит ошибки
C++ Ошибки при освобождении памяти
Ошибка при освобождении памяти C++
C++ Выделение памяти при перегрузке
Ошибка при освобождении памяти C++
C++ Утечка памяти при удалении
Вылетает при удалении памяти C++
Ошибка при освобождении памяти C++
Ошибка при освобождении памяти C++
C++ Выделение памяти при наследовании

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru