SPOJ LCS2(Longest Common Substring II - 아버지에게 접미사 로봇 업데이트)

1812. Longest Common Substring II Problem code: LCS2
 
 
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 a bit harder, for some 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 at most 10 lines, each line consists of no more than 100000 lowercase letters, representing a string.
Output
The length of the longest common substring. If such string doesn't exist, print "0"instead.
Example

Input:
alsdfkjfjkdsal
fdjskalajfkdsla
aaaajfaaaa

Output:
2

Notice: new testcases added
 
LCS와 차이가 별로 없습니다.이 문제를 먼저 쓸 걸 그랬어, 한 문제가 두 문제보다 낫다.
이 문제는 먼저 답안을 g2에 저장하여 하나의 결점의 최대 선택 가능한 길이를 나타낸다.
그러나 이렇게 움푹 패인 베카우스의 조상은 0으로 일치하는 것보다 작을 수도 있다.
그래서 상향 업데이트, 만약에 한 노드가 연하면len1을 얻을 수 있다면, 그의 조상은 반드시 step≤len1을 얻을 수 있다
그래서 g에게 부여된 초치는 step...
 

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
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<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;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 (200000+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 g[MAXN]={0},g2[MAXN];
int t[MAXN]={0},r[MAXN]={0};
int main()
{
//	freopen("spojLCS2.in","r",stdin);
	scanf("%s",s1+1);int n=strlen(s1+1);
	For(i,n) insert(s1[i]-'a');
	Rep(i,total+1) t[a[i].step]++;
	For(i,n) t[i]+=t[i-1];
	Rep(i,total+1) r[t[a[i].step]--]=i;
		
	Rep(i,total+1) g[i]=a[i].step;
	while (scanf("%s",s2+1)==1)
	{
		int now=0,len=0,m=strlen(s2+1);
		MEM(g2);
		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++;
			g2[now]=max(g2[now],len);
		}
		ForD(i,total+1)
		{
			int now=r[i];
			g2[a[now].pre]=max(g2[a[now].pre],g2[now]);
		}
		Rep(i,total+1) g[i]=min(g[i],g2[i]);
	}
	int ans=0;
	Rep(i,total+1) ans=max(ans,g[i]);
	printf("%d
",ans);
	return 0;
}