초록 추출

글에는 보통 글 전체를 요약하는 초록(abstract)이 들어 있다. 우리는 이 초록을 자동으로 생성하는 알고리즘을 실험하고 있다. 알고리즘은 하나의 글을 읽어 전체를 요약하는 초록을 만든다. 초록은 연속된 문단들에서 뽑아낸 "주제 문장"을 이어 붙여 만든다.

이 문제에서는 다음과 같이 정의한다.

• 글(article)은 하나 이상의 문단(paragraph)으로 이루어진다.
• 문단은 비어 있지 않은 줄들이 최대로 연속된 구간이다.
• 문장(sentence)은 문단 안에서 공백이 아닌 문자로 시작하고, .(마침표)·?·! 중 하나로 끝나며, 그 사이에 .·?·!를 하나도 더 포함하지 않는 최대 길이의 문자열이다. 하나의 문장은 여러 줄에 걸쳐 있을 수 있다.
• 단어(word)는 문장 안에서 알파벳 문자가 최대로 연속된 구간이다.

위 정의에서 "최대(maximal)"란 정의를 만족하는 가장 긴 구간만을 뜻하며, 그 부분 구간은 포함하지 않는다. 예를 들어 문장 "How now, brown cow?"에는 단어가 4개 있다. "now"는 단어이지만 "no", "ow" 등은 더 긴 알파벳 구간의 부분 구간이므로 단어가 아니다.

문단의 주제 문장(topic sentence)은 그 문단의 내용을 가장 잘 나타내는 하나의 문장이다. 다음과 같이 고른다. 각 문장 S에 대해, S에 들어 있는 서로 다른 단어 중 같은 문단에서 S보다 뒤에 오는 어떤 문장에도 나타나는 단어의 개수를 센다. 이 개수가 최대가 되는, 가장 앞선 문장을 주제 문장으로 선택한다.

문장이 3개 미만인 문단은 무시하며, 초록에 기여하지 않는다.

단어가 서로 같은지 비교할 때 대소문자 차이는 무시한다. 예를 들어 문장 "See what I see."에 들어 있는 서로 다른 단어는 4개가 아니라 3개이다.

입력은 하나 이상의 글로 이루어진다. 각 글은 *** 또는 ******만으로 이루어진 줄로 끝난다. 뒤쪽 문자열(******)은 전체 입력의 끝을 나타낸다.

• 각 글은 하나 이상의 문단으로 이루어진다. 각 문단은 하나 이상의 비어 있지 않은 줄로 이루어지며, 빈 줄이나 위에서 설명한 *** 또는 ****** 표시로 끝난다.
• 어떤 글도 500줄을 넘지 않는다. 어떤 줄도 150자를 넘지 않는다. 어떤 단어도 50자를 넘지 않는다.
• 입력에 나타나는 공백 문자는 빈칸(ASCII 32)과 줄바꿈 문자뿐이다.

각 글마다 초록을 출력한 뒤, ======(등호 6개)만으로 이루어진 줄을 출력한다.

각 초록은 위에서 설명한 방식으로 고른 주제 문장들을 입력에 나타난 순서대로 이어 붙여 만든다. 각 문장은 입력에 나타난 그대로 출력하고, 그 뒤에 줄바꿈을 넣는다.