两个最小循环位移的交集

C++ Hard strings

任务 «两个最小循环位移的交集»

给定两个由小写拉丁字母组成的字符串 s 和 t。需要找出最长的公共子串的长度，该子串是字符串 s 的某个循环移位和字符串 t 的某个循环移位的子串。循环移位是指将字符串的所有字符向左移动 k 个位置，而左侧移出的字符被移到末尾。字符串长度不超过 10^5。如果未找到公共子串，则输出 0。

在第一行给出一个字符串 s (1 ≤ |s| ≤ 10^5)。在第二行给出一个字符串 t (1 ≤ |t| ≤ 10^5)。字符串仅由小写拉丁字母组成。

输出一个整数——在某个循环移位s和某个循环移位t中出现的最长公共子串的长度。

输入

abc
def

输出

0

输入

bcd

输出

abc

main.cpp