Description：

输入 $2 $ 个字符串，输出这 $2 $ 个字符串的最长公共子串长度。

$1\le len \le 250000$

Solution：

建出 $A$ 的后缀自动机，把 $B$ 串在上面跑，如果沿转移边走到下一个节点，则 $++sum$ ，如果没有转移边，就不停跳 $par$ ，直到跳到根或有这个转移为止，这时 $sum=s[cur].maxl$ 再沿转移走一步， $++sum$ ，注意随时用 $sum$ 更新 $ans$ ，原理是 $par$ 树的祖先是他的后缀，所以能转移就转移，不能转移就尝试缩小子串长度。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 250010

char a[MAXL],b[MAXL];

struct node

{

	int tr[26];

	int par,maxl;

}s[MAXL << 1];

int ptr = 1,last = 1,root = 1;

int newnode(int k){++ptr;s[ptr].maxl = k;return ptr;}

void extend(int k)

{

	int p = last;

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	last = np;

	return;

}

int main()

{

	scanf("%s%s",a + 1,b + 1);

	int l = strlen(a + 1);

	for(int i = 1;i <= l;++i)extend(a[i] - 'a');

	l = strlen(b + 1);

	int cur = root;

	int sum = 0;

	int ans = 0;

	for(int i = 1;i <= l;++i)

	{

		if(s[cur].tr[b[i] - 'a'] != 0)

		{

			cur = s[cur].tr[b[i] - 'a'];

			++sum;

			ans = max(ans,sum); 

		}

		else

		{

			while(cur && s[cur].tr[b[i] - 'a'] == 0)cur = s[cur].par;

			if(cur == 0)cur = root,sum = 0;

			else

			{

				sum = s[cur].maxl + 1;

				cur = s[cur].tr[b[i] - 'a'];

				ans = max(ans,sum);

			}

		}

	}

	cout << ans << endl;

	return 0;

}