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

@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, у меня такая засада - вариант алфавита - слова латинского алфавита. Насчет того, что не может поместиться в оперативной памяти, об этом сказал преподаватель, а программа прогоняется на сервере, как на олимпиадах.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@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