Abstract Extract

Time limit1sMemory limit128 MB

Summary
For each article, pick the topic sentence of every paragraph with three or more sentences and print them in order.
Level

Medium5 of 10

Topics
String, Simulation, Hash map
Solved
No attempts yet

Problem

When writing an article, there is usually an abstract that summarizes the whole article. We are experimenting with an algorithm that generates such an abstract automatically. The algorithm reads an article and produces an abstract that summarizes it. The abstract is formed by joining the topic sentences taken from consecutive paragraphs.

For this problem:

  • An article consists of one or more paragraphs.
  • A paragraph is a maximal sequence of non-empty lines.
  • A sentence is a maximal sequence of characters within a paragraph that begins with a non-whitespace character, ends with a . (period), ?, or !, and contains no other occurrence of ., ?, or !. A single sentence may span several lines.
  • A word is a maximal sequence of alphabetic characters within a sentence.

Here maximal means we take only the longest sequence that matches the definition, not any of its subsequences. For example, the sentence "How now, brown cow?" contains four words. "now" is a word, but "no" and "ow" are not, because they are subsequences of a longer sequence of alphabetic characters.

The topic sentence of a paragraph is the single sentence that best describes the paragraph. We choose it as follows: for each sentence S, count the distinct words in S that also occur in some later sentence of the same paragraph; the topic sentence is the earliest sentence that maximizes this count.

Paragraphs with fewer than three sentences are ignored and do not contribute to the abstract.

When comparing words, differences in upper and lower case are ignored. For example, the sentence "See what I see." contains three distinct words, not four.

Input

The input consists of one or more articles. Each article is terminated by a line containing only *** or ******. The latter (******) marks the end of the entire input.

  • Each article contains one or more paragraphs. Each paragraph consists of one or more non-empty lines and is terminated by an empty line or by the *** or ****** markers described above.
  • No article is longer than 500 lines. No line contains more than 150 characters. No word contains more than 50 characters.
  • The only whitespace characters in the input are blanks (ASCII 32) and line terminators.

Output

For each article, print its abstract followed by a line containing ====== (six equal signs).

Each abstract is formed from the topic sentences, selected as described above, in the order they occur in the article. Print each sentence exactly as it appears in the input, followed by a line break.

Examples3

  1. Example 1

    Input
    Hello world! Everyone should greet the entire world in a friendly
manner. Wouldn’t that make the world a more friendly place?

This is not a sentence
***
From: The Wright Brothers’ Aeroplane.

By Orville and Wilbur Wright

In 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 by
Lilienthal, Mouillard, and Chanute, to soaring flight. Our sympathies
were with the latter school, partly from impatience at the wasteful
extravagance of mounting delicate and costly machinery on wings
which no one knew how to manage, and partly, no doubt, from the
extraordinary charm and enthusiasm with which the apostles of soaring
flight set forth the beauties of sailing through the air on fixed
wings, 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 be
flown as a kite, with a man on board, in winds from 15 to 20 miles an
hour. But, upon trial, it was found that much stronger winds were
required to lift it. Suitable winds not being plentiful, we found it
necessary, in order to test the new balancing system, to fly the machine
as a kite without a man on board, operating the levers through cords
from the ground. This did not give the practice anticipated, but it
inspired 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 not
with any expectation of recovering the money we were expending on it, he
gave us much encouragement. At our invitation, he spent several weeks
with 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 also
witnessed one flight of the power machine near Dayton, Ohio, in October,
1904.
******
    Expected output
    Everyone should greet the entire world in a friendly
manner.
======
The first,
represented by such men as Professor Langley and Sir Hiram Maxim,
gave chief attention to power flight; the second, represented by
Lilienthal, Mouillard, and Chanute, to soaring flight.
Our machine was designed to be
flown as a kite, with a man on board, in winds from 15 to 20 miles an
hour.
When he learned that we were interested in flying as a sport, and not
with any expectation of recovering the money we were expending on it, he
gave us much encouragement.
======

  2. Example 2

    Input
    Cats like fish. Fish like water. Water is nice.
******
    Expected output
    Cats like fish.
======

  3. Example 3

    Input
    Red blue green. Blue green red. Green stands alone.
***
One two three. Two three four. Four five six.
******
    Expected output
    Red blue green.
======
One two three.
======