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

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

Восстановить пароль Регистрация
 
kilobitt
0 / 0 / 0
Регистрация: 27.12.2015
Сообщений: 1
27.12.2015, 18:37     Поиск подстроки минимальной длины в строке (файловый ввод/вывод) #1
Задача 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 .
Заранее благодарю всех. кто поможет.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2015, 18:37     Поиск подстроки минимальной длины в строке (файловый ввод/вывод)
Посмотрите здесь:

файловый ввод-вывод C++
C++ файловый ввод-вывод
Файловый ввод/вывод C++
C++ Файловый ввод-вывод
C++ Файловый ввод вывод
C++ Файловый ввод / вывод
C++ Файловый ввод вывод
Файловый ввод-вывод, ввод с клавиатуры и обработка массива структур C++

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

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

Текущее время: 13:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru