<PREV Problem:
NEXT>
Solved by 53 users: ...
UserDateAttemptTimeCMSC
adamant13 jan 2015C++1700.06365 
adamant13 jan 2015C++1900.06365 
adamant13 jan 2015C++2500.06371 
adamant13 jan 2015C++2300.05377 
adamant13 jan 2015C++2400.05383 
DPR-pavlin02 dec 2010C++200.57412 
yana03 dec 2010C++500.57412 
kmilo04 mar 2011C++100.04419 
JohnJones_00129 sep 2008C++600.54437 
topspin31 jul 2010Kylix601.70463 
ignat25 apr 2010C++200.45473 
topspin31 jul 2010Kylix500.38475 
MasterYoda29 jul 2009C++300.05479 
topspin31 jul 2010Kylix400.37484 
isa10 apr 2013Java100.98491 
MasterYoda29 jul 2009C++200.04515 
DAV11 jul 2009C++200.12520 
Languages
C++
42
Java
6
Kylix
4
FPC
3
Ruby
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Antiplagiarism II

Time limit = 2 second(s)

Memory limit = 128 Mb

MIPT professor in theoretical physics is in possession of a huge articles library. He has already noticed for a number of times scientists copy introductions, bibliographic references and even more from each other.

Now he wants to find two articles in which the common substring has the maximum length.

In order to stay in MIPT you are to help him.

The articles are preprocessed for you: newlines, commas, digits, and everything apart from latin characters is already removed from them.

The library contain some very authentic articles, which contain a large number of repetitions of one or two characters — the articles of Bamba-Yumba tribe. These articles are very deep. Please make sure your program does not try to be wise and understand them entirely.

Input Two input lines contain two words consisting of latin characters. The length of each string does not exceed 100000 characters.

Output Theee numbers, L, N, M. L: The length of the longest substring. N, M: 0-based indices of the first characters of this substring in the first and second articles respectively. Output three zeroes if the articles do not contain common substrings.

Input#1
abrakadabrabra
krabrakrabrakra
Output#1
5 9 1
Input#2
aaaaabraaaaaaaa
brakraaaaaaak
Output#2
8 6 4


Author:
Artem Voroztsov, MIPT individual contest, September 21 2008
September 21 2008

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 18.232.51.247