Аннотация Extract
Когда пишутся статьи, обычно включается раздел аннотации, который кратко излагает содержание всей статьи. Мы разрабатываем алгоритм для автоматической генерации таких аннотаций. Алгоритм анализирует статью и создает аннотацию, объединяя "тематические предложения", извлеченные из последовательных абзацев.
Для этой задачи:
Статья состоит из одного или нескольких абзацев.
Абзац — это максимальная последовательность непустых строк.
Предложение — это максимальная последовательность символов в абзаце, которая начинается с непробельного символа, заканчивается на '.', '?', или '!', и не содержит других вхождений этих знаков.
Слово — это максимальная последовательность алфавитных символов в предложении.
Термин "максимальная" в этих определениях означает, что нас интересуют только самые длинные последовательности, соответствующие определению, а не их подпоследовательности. Например, предложение 'How now, brown cow?' содержит четыре слова. 'now' является словом в этом предложении, но 'no', 'ow' и т.д. не являются словами, так как они не максимальны — они являются подпоследовательностями более длинной последовательности алфавитных символов.
Тематическое предложение для абзаца — это единственное предложение в абзаце, которое лучше всего описывает его содержание. Для наших целей мы выберем самое раннее предложение в абзаце, которое максимизирует количество различных слов в S, которые также встречаются в любом следующем предложении в том же абзаце.
Абзацы с менее чем тремя предложениями игнорируются и не будут включены в аннотацию.
При сравнении слов на уникальность игнорируются различия в верхнем/нижнем регистре. Например, предложение "See what I see." содержит три различных слова, а не четыре.
Входные данные
Ввод состоит из одной или нескольких статей. Каждая статья завершается строкой, содержащей только "***" или "******". Последняя строка ("******") указывает на конец всего набора ввода.
Каждая статья будет содержать один или несколько абзацев. Каждый абзац будет состоять из одной или более непустых строк и завершаться пустой строкой или маркерами "***" или "******", описанными выше.
Ни одна статья не будет длиннее 500 строк; ни одна строка не будет содержать более 150 символов. Ни одно слово не будет содержать более 50 символов.
Единственными пробельными символами во вводе будут пробелы (ASCII 32) и терминаторы строк.
Выходные данные
Для каждого документа напечатайте аннотацию, за которой следует строка, содержащая "======" (шесть знаков равенства).
Каждая аннотация будет сформирована из последовательности тематических предложений, выбранных, как описано выше, в порядке их появления в входном документе. Каждое предложение должно быть напечатано точно так, как оно появляется во вводе, и должно быть завершено разрывом строки.
Пример ввода
Hello world! Everyone should greet the entire world in a friendlymanner. Wouldn’t that make the world a more friendly place?This is not a sentence***From: The Wright Brothers’ Aeroplane.By Orville and Wilbur WrightIn the field of aviation there were two schools. The first,represented by such men as Professor Langley and Sir Hiram Maxim,gave chief attention to power flight; the second, represented byLilienthal, Mouillard, and Chanute, to soaring flight. Our sympathieswere with the latter school, partly from impatience at the wastefulextravagance of mounting delicate and costly machinery on wingswhich no one knew how to manage, and partly, no doubt, from theextraordinary charm and enthusiasm with which the apostles of soaringflight set forth the beauties of sailing through the air on fixedwings, deriving the motive power from the wind itself.We began our active experiments at the close of this period, in October,1900, at Kitty Hawk, North Carolina. Our machine was designed to beflown as a kite, with a man on board, in winds from 15 to 20 miles anhour. But, upon trial, it was found that much stronger winds wererequired to lift it. Suitable winds not being plentiful, we found itnecessary, in order to test the new balancing system, to fly the machineas a kite without a man on board, operating the levers through cordsfrom the ground. This did not give the practice anticipated, but itinspired confidence in the new system of balance.In the summer of 1901 we became personally acquainted with Mr. Chanute.When he learned that we were interested in flying as a sport, and notwith any expectation of recovering the money we were expending on it, hegave us much encouragement. At our invitation, he spent several weekswith us at our camp at Kill Devil Hill, four miles south of Kitty Hawk,during our experiments of that and the two succeeding years. He alsowitnessed one flight of the power machine near Dayton, Ohio, in October,1904.****** Пример выводаEveryone should greet the entire world in a friendlymanner.======The first,represented by such men as Professor Langley and Sir Hiram Maxim,gave chief attention to power flight; the second, represented byLilienthal, Mouillard, and Chanute, to soaring flight.Our machine was designed to beflown as a kite, with a man on board, in winds from 15 to 20 miles anhour.When he learned that we were interested in flying as a sport, and notwith any expectation of recovering the money we were expending on it, hegave us much encouragement.======