Чтение строки неограниченной длины и её параллельная обработка

@mishula · Регистрация: 01.10.2014

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

Здравствуйте. В ходе реализации алгоритма для поиска возникла проблема в том, что в условии написано, что входная строка может быть сколь угодно большой длины (а значит, может не поместиться в оперативной памяти). Предположим, что длина слова всё таки имеет какую то максимальную длину, к примеру 4096. Я нашёл такое решение проблемы. Создаём вектор (приходится самому писать, так как контейнером не разрешают пользоваться). Каждое считанное слово отправляем туда, то есть получается вектор указателей на char. И как только общее кол-во считанных слов равно 50, передаем вектор в функцию для поиска в ней образца. То есть примерный алгоритм так выглядит:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
char tmp[2048];
while (cin>>tmp) {
       i++;
       len = strlen(tmp)+1;
       tmp[len] = '\0';
       Resize(&v2,len);
       strcpy(v2.letter[v2.size-1].str,tmp);//перенесли данные в вектор
       if (i == cap) {//кол-во слов равно 50
           KMP(&v2,&v1,sum*(cap - 1));//сама функция
           sum++;
           Destroy(&v2);
           for (i=0; i<v1.size; i++)   
               Resize(&v2,strlen(v2.letter[i].str)+1); //особенности алгоритма КМП, пока это не играет роли
           i = 0;
       }
   }

Но у меня появились мысли, что на самом деле всё равно все операции происходят только после считывания всей строки, то есть вся строка считывается и держится в ОП. Правильны ли мои опасения. Если да, то посоветуйте пути решения этой проблемы.

@IVSasha · 05.11.2015, 23:02

Сообщение от mishula

char tmp[2048];

Создайте массив большего размера. 1Гб, 2Гб, 3Гб... Неужели не хватит для строки?

C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
 
char ar[1500000000];
 
int main()
{
    
    system("pause");
    return 0;
}

@nmcf · 05.11.2015, 23:11

Почему именно 50? По одному слову обрабатывать нельзя?

@mishula · 06.11.2015, 00:12 **[ТС]**

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

@nmcf · 06.11.2015, 10:47

Алгоритм этот ищет подстроку в строке, ну понятно, что строка должна быть длиннее. А ты делишь строку на слова, какая тогда разница сколько их, если поиск в пределах каждого слова идёт? Или я чего-то не понял?

@Dimension · 06.11.2015, 11:03

Сообщение от mishula

а значит, может не поместиться в оперативной памяти

Это вы сами придумали или там так и написано?

Добавлено через 2 минуты

Сообщение от mishula

Для алгоритма Кнутта-Морриса-Пратта нужно, чтобы строка, в которой ищем была в несколько раз больше образц

образец может быть равен строке даже ,что тогда делать будете?

@mishula · 06.11.2015, 12:24 **[ТС]**

Dimension, nmcf, у меня такая засада - вариант алфавита - слова латинского алфавита. Насчет того, что не может поместиться в оперативной памяти, об этом сказал преподаватель, а программа прогоняется на сервере, как на олимпиадах.

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	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 Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	05.11.2015, 23:11
	Почему именно 50? По одному слову обрабатывать нельзя? 0

@mishula 0 / 0 / 1 Регистрация: 01.10.2014 Сообщений: 87
	06.11.2015, 00:12 [ТС]
	nmcf, это слова, среди которых ищем. Для алгоритма Кнутта-Морриса-Пратта нужно, чтобы строка, в которой ищем была в несколько раз больше образца. Мои опасения правильны? 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	06.11.2015, 10:47
	Алгоритм этот ищет подстроку в строке, ну понятно, что строка должна быть длиннее. А ты делишь строку на слова, какая тогда разница сколько их, если поиск в пределах каждого слова идёт? Или я чего-то не понял? 0

@mishula 0 / 0 / 1 Регистрация: 01.10.2014 Сообщений: 87
	06.11.2015, 12:24 [ТС]
	Dimension, nmcf, у меня такая засада - вариант алфавита - слова латинского алфавита. Насчет того, что не может поместиться в оперативной памяти, об этом сказал преподаватель, а программа прогоняется на сервере, как на олимпиадах. 0