NOTE: YOU CAN SOLVE THIS PROBLEM USING SUFFIX ARRAY!!!
The cows enjoy mooing at the barn because their moos echo back,
although sometimes not completely. Bessie, ever the excellent
secretary, has been recording the exact wording of the moo as it
goes out and returns. She is curious as to just how much overlap
there is.
Given two lines of input (letters from the set a..z, total length
in the range 1..80), each of which has the wording of a moo on it,
determine the greatest number of characters of overlap between one
string and the other. A string is an overlap between two other
strings if it is a prefix of one string and a suffix of the other
string.
By way of example, consider two moos:
moyooyoxyzooo
yzoooqyasdfljkamo
The last part of the first string overlaps 'yzooo' with the first
part of the second string. The last part of the second string
overlaps 'mo' with the first part of the first string. The largest
overlap is 'yzooo' whose length is 5.
POINTS: 50
PROBLEM NAME: echo
INPUT FORMAT:
* Lines 1..2: Each line has the text of a moo or its echo
SAMPLE INPUT:
abcxxxxabcxabcd
abcdxabcxxxxabcx
OUTPUT FORMAT:
* Line 1: A single line with a single integer that is the length of
the longest overlap between the front of one string and end of
the other.
SAMPLE OUTPUT:
11
OUTPUT DETAILS:
'abcxxxxabcx' is a prefix of the first string and a suffix of the second
string.
[Vietnamese Translation]
Bài 3: Barn Echoes [50 points] [Traditional, 2009]
Những con bò thích rống lên ở kho bởi vì những tiếng bò rống của họ
vang vọng trở, mặc dù đôi khi không hoàn toàn. Bessie, từng là thư ký
xuất sắc, đã và đang ghi lại cách diễn đạt chính xác của tiếng bò rống
khi nó ra ngoài và trở lại. Cô ấy tò mò đối với chỉ bao nhiêu tiếng rồng
chồng lên nhau.
Dữ liệu được đưa ra trên hai dòng(với độ dài trong phạm vi 1..80),
mỗi dòng có cách diễn đạt một tiếng bò rống trên nó, tìm ra số kí tự lớn nhất
của sự chồng chéo giữa một xâu và một xâu khác. Một xâu là một sự chồng chéo
giữa hai xâu khác nếu nó là một tiền tố một xâu và một hậu tố của xâu khác.
Qua ví dụ, suy nghĩ về hai tiếng bò rống:
moyooyoxyzooo
yzoooqyasdfljkamo
Phần cuối cùng của xâu đầu chồng chéo xâu đầu tiên 'yzooo' với
phần đầu tiên của xâu thứ hai. Phần cuối cùng của xâu thứ hai 'mo'
chồng chéo với phần đầu tiên của xâu đầu tiên.
Sự chồng chéo dài nhất 'yzooo' có độ dài là 5.
ĐIỂM: 50
TÊN BÀI: echo
KHUÔN DẠNG DỮ LIỆU VÀO:
* Các dòng 1..2: Mỗi dòng có một xâu thể một tiếng bò rống hoặc tiếng vọng của nó.
DỮ LIỆU VÀO MẪU (tệp tin echo.in):
abcxxxxabcxabcd
abcdxabcxxxxabcx
KHUÔN DẠNG KẾT QUẢ:
* Dòng 1: Một xâu duy nhất với một số nguyên duy nhất là chiều dài của chồng
chéo dài nhất giữa mặt trước một xâu và cuối của khác.
KẾT QUẢ MẪU (tệp tin echo.out):
11
CHI TIẾT KẾT QUẢ:
'abcxxxxabcx' Là một tiền tố của xâu đầu tiên và một hậu tố của xâu thứ hai.
[Chinese Translation]
第三題: 牛棚回聲 [50分] [傳統題目, 2009]
奶牛們灰常享受在牛欄中哞叫，因為她們可以聽到她們哞聲的回音。雖然有時候並不能完全聽到
完整的回音。Bessie曾經是一個出色的秘書，所以她精確地紀錄了所有的哞叫聲及其回聲。她
很好奇到底兩個聲音的重復部份有多長。
輸入兩個字符串（長度為1到80個字母），表示兩個哞叫聲。你要確定最長的重復部份的長度。
兩個字符串的重復部份指的是同時是一個字符串的前綴和另一個字符串的後綴的字符串。
我們通過一個例子來理解題目。考慮下面的兩個哞聲：
moyooyoxyzooo
yzoooqyasdfljkamo
第一個串的最後的部份"yzooo"跟第二個串的第一部份重復。第二個串的最後的部份"mo"跟第一
個串的第一部份重復。所以"yzooo"跟"mo"都是這2個串的重復部份。其中，"yzooo"比較長，
所以最長的重復部份的長度就是5。
分值: 50
題目名稱: echo
輸入格式:
* 前兩行: 每一行是1個字符串表示奶牛的哞聲或它的回聲。
樣例輸入 (文件 echo.in):
abcxxxxabcxabcd
abcdxabcxxxxabcx
輸出格式:
* 第一行: 包含一個單獨的整數表示輸入的2個字符串中，一個字符串的前綴和另一個字符串的後
綴的最長的重復部份的長度。
樣例輸出 (文件 echo.out):
11
輸出細節:
"abcxxxxabcx"是第一個字符串的前綴和第二個字符串的後綴。