Description：

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。位置不同的算多个。

$1\leqslant l_1,l_2\leqslant 2\times 10^5$

Solution：

先建出广义后缀自动机，然后分别求两个的 $Right$ 集合大小，但是由于在建广义后缀自动机的时候可能有的节点出边会改变，所以要在 最后 把两个的主链经过的点 $Right$ 集合依次加一，然后再拓扑排序出两个字符串的 $Right$ 集合大小，最后的答案就是： $$ ans=\sum_{i} siz[0][i]\times siz[1][i]\times (s[i].maxl-s[s[i].par].maxl) $$ 大概就是在第一个串中选择的方案数乘在第二个串中的方案数再乘上这个节点代表的字符串数量。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXL 200010

char a[MAXL],b[MAXL];

struct node

{

	int par,maxl;

	int tr[26];

}s[MAXL << 2];

int siz[2][MAXL << 2];

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

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

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 c[MAXL << 2],p[MAXL << 2];

int main()

{

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

	int l1 = strlen(a + 1);

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

	last = root;

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

	int l2 = strlen(b + 1);

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

	for(int i = 1,k = root;i <= l1;++i)

	{

		k = s[k].tr[a[i] - 'a'];

		++siz[0][k];

	}

	for(int i = 1,k = root;i <= l2;++i)

	{

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

		++siz[1][k];

	}

	for(int i = 1;i <= max(l1,l2);++i)c[i] = 0;

	for(int i = 1;i <= ptr;++i)++c[s[i].maxl];

	for(int i = 1;i <= max(l1,l2);++i)c[i] += c[i - 1];

	for(int i = ptr;i >= 1;--i)p[c[s[i].maxl]--] = i;

	for(int i = ptr;i >= 1;--i)

	{

		siz[0][s[p[i]].par] += siz[0][p[i]];

		siz[1][s[p[i]].par] += siz[1][p[i]];

	}

	long long ans = 0;

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

	{

		ans += 1ll * siz[0][i] * siz[1][i] * (s[i].maxl - s[s[i].par].maxl); 

	} 

	cout << ans << endl;

	return 0;

}