<PREV Problem:
NEXT>
Solved by 53 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 = 23.20.13.165