A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

Example

Input:alsdfkjfjkdsalfdjskalajfkdslaOutput:3 题解： 哈哈很意外啊，在电脑城随便找台机子用洛谷在线IDE 1A这题啊 讲讲思路: 以A建立SAM 让B在SAM上匹配 可以类比于kmp思想，我们知道在Parent树上，fa是当前节点的子集，也就是说满足最大前缀，利用这个就可以做题了 步骤如下： 1.如果满足ch[p][c]存在，那么就直接走就是了，和AC自动机类似，len++ 2.如果不存在，那么就沿fa上跳，找到最大dis[fa]且满足存在c这个儿子的.类似于跳fail链 3.跳到根就直接初始化，重新开始

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 const int N=550005; 8 char S[N];int n=0,cnt=1,cur=1,last=1,ch[N][26],fa[N],dis[N]; 9 void build(int c){10     last=cur;cur=++cnt;dis[cur]=++n;11     int p=last;12     for(;p && !ch[p][c];p=fa[p])ch[p][c]=cur;13     if(!p)fa[cur]=1;14     else{15         int q=ch[p][c];16         if(dis[q]==dis[p]+1)fa[cur]=q;17         else{18             int nt=++cnt;dis[nt]=dis[p]+1;19             memcpy(ch[nt],ch[q],sizeof(ch[q]));20             fa[nt]=fa[q];fa[q]=fa[cur]=nt;21             for(;ch[p][c]==q;p=fa[p])ch[p][c]=nt;22         }23     }24 }25 int ans=0;26 void Flr()27 {28     int p=1,nxt,lt;29     scanf("%s",S);30     int l=strlen(S),len=0,c;31     for(int i=0;i
          
           lt)lt=dis[p],nxt=p;40 p=fa[p];41 }42 if(nxt)43 p=ch[nxt][c],len=dis[nxt]+1;44 else45 p=1,len=0;46 }47 if(len>ans)ans=len;48 }49 printf("%d\n",ans);50 }51 void work()52 {53 scanf("%s",S);54 for(int i=0,l=strlen(S);i