时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
Mr.Colorful recently purchased a smart bluetooth speaker. He was quite satisfied with the speaker, except that something may went wrong when the speaker responds to him.
One day, Mr.Colorful found that the speaker produced a weird sentence, but he could not remember what exactly it said.
Based on impressions, Mr.Coloful was sure that the speaker wanted to say a sentence
, a string consisting of only lower case letters.
He believed that the sentence he heard sounded weird because a nonempty subinterval of must have been repeated immediately after its occurrence.
Formally speaking, a string is said to be a weird sentence originated from
, if and only if there exists two integers
, such that
,
where "+" means string concatenation and means the substring of
located at
.
Note that denotes an empty string when
.
Mr.Colorful opened the log of his speaker. The log is also a string
consisting of only lower case letters.
Given , help Mr.Colorful to find the longest substring of
such that it is a weird sentence originated from
.
If there are multiple such strings, please output the string with the leftmost start position.
输入描述:
The input consists of:
One line containing a string, the log of the speaker.
One line containing a string, the sentence that Mr.Colorful believed the speaker originally wanted to say.
输出描述:
If in the log
and
seperated by a space, denoting the location of the longest weird sentence (the string is 1-indexed). You need to ensure that
Otherwise, output
.