1811. Longest Common Substring

Problem code: LCS

 

 

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

 

本题要求2个字符串的LCS.

那么先将A串读入，再在A串上匹配B串显然

但是一个结点能表示的后缀有|maxS|-|minS|+1个。

那么就这样：

假设当前在结点x，下一个B串要匹配的字母为c

如果x有ch[c]，走过去len+1

否则找pre，更新len=pre的maxS

理由如下：

设原有串=ababd,babd,abd ,匹配为其中某一个

不存在abdx无法匹配.

取pre=bd,d,(由定义可知不存在‘dc存在匹配,bdc不存在’的情况，故它俩能为1个状态)

那么len=pre的maxS(step)

否则返回根,len=0

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i
             
              =0;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (100000007)#define MAXN (500000+10)long long mul(long long a,long long b){return (a*b)%F;}long long add(long long a,long long b){return (a+b)%F;}long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}typedef long long ll;char s1[MAXN],s2[MAXN];struct node{ int pre,step,ch[26]; char c; node(){pre=step=c=0;memset(ch,sizeof(ch),0);}}a[MAXN];int last=0,total=0;void insert(char c){ int np=++total;a[np].c=c+'a',a[np].step=a[last].step+1; int p=last; for(;!a[p].ch[c];p=a[p].pre) a[p].ch[c]=np; if (a[p].ch[c]==np) a[np].pre=p; else { int q=a[p].ch[c]; if (a[q].step>a[p].step+1) { int nq=++total;a[nq]=a[q];a[nq].step=a[p].step+1; a[np].pre=a[q].pre=nq; for(;a[p].ch[c]==q;p=a[p].pre) a[p].ch[c]=nq; }else a[np].pre=q; } last=np;}int main(){// freopen("spojLCS.in","r",stdin); scanf("%s%s",s1+1,s2+1);int n=strlen(s1+1),m=strlen(s2+1); For(i,n) insert(s1[i]-'a'); int now=0,ans=0,len=0; For(i,m) { char c=s2[i]-'a'; while (now&&!a[now].ch[c]) now=a[now].pre,len=a[now].step; if (a[now].ch[c]) now=a[now].ch[c],len++; ans=max(ans,len); } printf("%d\n",ans); return 0;}