Intersection of minimal cyclic shifts

C++ Hard strings

Task «Intersection of minimal cyclic shifts»

Given two strings s and t, consisting of lowercase Latin letters. It is necessary to find the length of the longest common substring that is a substring of some cyclic shift of string s and some cyclic shift of string t. A cyclic shift is a permutation of the characters of a string where all characters are shifted k positions to the left, and the characters that fall off on the left are moved to the end. The length of the strings does not exceed 10^5. If no common substring is found, output 0.

Input Format

In the first line, a string s is given (1 ≤ |s| ≤ 10^5). In the second line, a string t is given (1 ≤ |t| ≤ 10^5). The strings consist only of lowercase Latin letters.

Output Format

Output a single integer — the length of the longest common substring that appears in some cyclic shift of s and some cyclic shift of t.

Examples

Example 1

INPUT

abc
def

OUTPUT

0

Example 2

INPUT

bcd

OUTPUT

abc

main.cpp