Description：

给定一个只包含小写字母的字符串 $S$ ，求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

$1\le n \le 10^6$

Solution：

对 $S$ 建出 $SAM$ ，当新建一个 $np$ 节点时 $siz[np]++$ ，最后在 $parent$ 树上 $dfs$ 求和，由于 $parent$ 树的父亲是每个儿子的后缀，所以儿子的出现次数应累加到父亲上，由于 $nq$ 是后缀状态的转移，所以并不会产生新子串。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXL 1000010

char c[MAXL];

struct node

{

	int tr[26],par,maxl;

}s[MAXL << 1];

int root,last,ptr = 0;

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

int siz[MAXL << 1];

void extend(int c)

{

	int p = last;

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

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

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

	else

	{

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

		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[c] == q;p = s[p].par)s[p].tr[c] = nq;

		}

	}

	last = np;

	return;

}

struct edge

{

	int to,nxt;

}e[MAXL << 1];

int lin[MAXL << 1] = {0};

int edgenum = 0;

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

typedef long long ll;

ll res = 0;

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs(e[i].to);

		siz[k] += siz[e[i].to];

	}

	if(siz[k] != 1)res = max(res,(ll)siz[k] * s[k].maxl);

	return;

}

int main()

{

	scanf("%s",c);

	int l = strlen(c);

	last = root = ptr = 1;

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

	for(int i = 2;i <= ptr;++i)add(s[i].par,i);

	dfs(1);

	cout << res << endl;

	return 0;

}