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

Поиск подстроки минимальной длины в строке (файловый ввод/вывод) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Компилятор ругается на fopen http://www.cyberforum.ru/cpp-beginners/thread1626986.html
#include<iostream> #include<stdio.h> #include <string.h> #define MAX 50 using namespace std; // Приоритет операций int prioritet(char var) {
C++ Как реализовать поиск значения,которое находится в стеке? нужно найти значение.Значение находится в стеке.Как реализовать поиск? Пробовал через массив сделать что-то не получается вот код #include "stdafx.h" #include <stdlib.h> #include <string.h> #include <conio.h> #include <stdio.h> #include <iostream> #define ERROR_OPEN_FILE -3 http://www.cyberforum.ru/cpp-beginners/thread1626980.html
Ошибка "Expression expected" C++
#pragma hdrstop #pragma argsused #ifdef _WIN32 #include <tchar.h> #else typedef char _TCHAR; #define _tmain main #endif #include <iostream>
Конвертировать двухбайтовую строку в однобайтовую C++
Как перевести без потери данных? Из wchar_t wPass В byte bPass Подсказали так: std::copy(wPass, 256, reinterpret_cast<WCHAR *>(bPass)); Не работает...
C++ Написать программу решения простейшего дифференциального уравнения с запаздывающим аргументом http://www.cyberforum.ru/cpp-beginners/thread1626945.html
Нужно запрограммировать решение простейшего дифференциального уравнения с запаздывающим аргументом: Кто нибудь может кинуть пример подобной программы, подсказать библиотеку для интегрирования или как вообще это кодируют, хоть что-нибудь ?
C++ Функция вычисляющая стоимость товара с налогом напишите функцию add_tax типа void.у неё два формальных параметра :taxRate,значение которого представляет налог с продажи в процентах ,и cost,значение которого представляет стоимость товара без налога.Функция изменяет значение параметра cost ,что бы оно включало налог с продажи. подробнее

Показать сообщение отдельно
kilobitt
0 / 0 / 0
Регистрация: 27.12.2015
Сообщений: 1
27.12.2015, 18:37     Поиск подстроки минимальной длины в строке (файловый ввод/вывод)
Задача I. Рефераты
Имя входного файла: input.txt или стандартный поток ввода
Имя выходного файла: output.txt или стандартный поток вывода
Ограничение по времени: 3 секунды
Ограничение по памяти: 512 мегабайт
Флорен и её друзьям на уроке английского поручили подготовить рефераты по предоставлен-
ным статьям — каждому ученику была выдана отдельная статья, по которой он должен сделать
реферат. В рамках данной задачи статьёй называется непустая строка, состоящая из строчных
символов английского алфавита. Рефератом статьи называется непустая строка, являющаяся под-
строкой данной статьи. Все ученики должны будут представить свои рефераты у доски. Чтобы
их было интереснее слушать, учитель потребовал, чтобы каждый из представленных рефератов не
встречался как подстрока ни в одном тексте статьи, кроме той, из текста которой он был образован.
Так как Флорен и её друзья не любят тратить много времени на выполнение домашнего задания,
они попросили вас помочь им выбрать для каждой статьи реферат минимальной длины, который не
является подстрокой никакой другой статьи, либо сообщить, что выбрать реферат, удовлетворяю-
щий требованию учителя, невозможно. Если для какого-то ученика возможно образовать несколько
кратчайших рефератов, из них требуется выбрать лексикографически минимальный. Вы, конечно
же, согласились им помочь.
Формат входных данных
В первой строке ввода записано одно число n (1 ⩽ n ⩽ 100 000) — количество статей.
Следующие n строк содержат описания статей. Каждая статья представляет собой последова-
тельность строчных символов английского алфавита si (1 ⩽ |si| ⩽ 500 000).
Обозначим через L суммарную длину всех статей, то есть L =∑ni=1|si|. Гарантируется, что во всех тестах L ⩽ 500 000.
Формат выходных данных
Выведите n строк — рефераты, соответствующие указанным статьям, в том же порядке, что и
во входных данных, или символ ‘?’, если для статьи не существует подходящего реферата.
Примеры
ввод
4
bear
deer
read
beard
вывод
?
de
ad
rd
ввод
3
xerox
roxwill
williams
вывод
e
xw
a
я пробовал делать так: брал префикс функцию от каждой строки относительно всех остальных строк, при этом я постепенно уменьшал строку, от которой брал префикс-функцию, удаляя каждый раз по одному начальному символу. И, исходя из этого выбирал нужный минимальный реферат.
вот ссылка на мой код ( если нужно ) http://pastebin.com/tLYYgpk9
Но при моём решение выдаёт long time даже при L=5000 .
Заранее благодарю всех. кто поможет.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 17:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru