Limits 1s, 512 MB

"Let me give you a clue. The happiest man on Earth would look into the mirror and see only himself, exactly as he is." - was the words Albus Dumbledore told Harry Potter long ago.

But why is Harry reminiscing about the mirror anyway? He has come to help his friend Hermione Granger in inventing a new spell to battle dementors. Being a talented wizard, you probably already know that the most effective weapon against dementors so far is a Patronus, which is basically a manifestation of good will and happiness. And Hermione wants to estimate the happiness in some spells, because she thinks the happier a spell is, the more effective it will be against dementors. Clever, isn’t she?! That’s where the Mirror of Erised comes in. When the happiest man on Earth looks into the mirror, the mirror shows back only himself in reflection. On the golden frame of the mirror, a writing is inscribed - "erised straeh ruoy tub ecaf ruoy ton wohs i". Hermione noted that when this text is reversed and the spaces are rearranged, it becomes "i show not your face but your hearts desire"!

So from these clues of the mirror, Hermione figured, if a spell is the same when it is reflected, it is a happy spell and thus it will work effectively on dementors, and here, reflection actually means reversal i.e. a string is happy when it is the same after reversal i.e. it is palindromic. Now, Hermione knows a very strong spell, and so does Harry. Hermione thinks any new spell that is common to both of these strong spells will also be considerably strong. The new spell needs to be happy too of course, to work better on dementors. Using a technique she learned in RUET (Rajshahi University of Enchantment and Transfiguration), Hermione has found strings (string S1S_1 and string S2S_2) that are equivalent to the strong spells Harry and she know. Now, they just need to find the longest happy substring that is common in both S1S_1 and S2S_2, which termed as LCHS.

Since Harry and Hermione are quite busy with the other parts of their research, for assistance, they have sent for you, the best wizard of RUET. Can you help them out by finding the length of the LCHS of S1S_1 and S2S_2?

Input

The input will contain two strings S1S_1 and S2S_2, each string in a single line, 1Si1051 ≤ |S_i| ≤ 10^5. Here Si|S_i| means the length of the ii-th string SiS_i.

Remember S1S_1 and S2S_2 will contain lowercase English alphabets only.

Output

Print a single integer - length of the LCHS of S1S_1 and S2S_2.

Samples

InputOutput
abcdcthohtn
xcdcythohtp
5
InputOutput
axppxdhdhhdhdcfc
ppxdhhdxdhd
4

Submit

Login to submit.

Statistics

55% Solution Ratio
YouKnowWhoEarliest, Aug '19
Kuddus.6068Fastest, 0.0s
ShadowMeLightest, 3.7 MB
TahseenShortest, 1031B
Toph uses cookies. By continuing you agree to our Cookie Policy.