题目链接
前置知识
后缀数组或后缀自动机
前一个百度即可查获大量资料
后一个推荐hihocoder上的全套教程，题库搜索“后缀自动机”即可找到
解析
方法一：后缀数组
链接大法：https://blog.csdn.net/A_Comme_Amour/article/details/79987498
方法二：后缀自动机
回想构建后缀自动机的过程，不难发现每增加一个字符，增加的本质不同的子串就是(new\_node->maxlen - new\_node->link->maxlen)
而拆出来的点是不产生贡献的
构建自动机过程中统计答案即可
代码（后缀自动机）
学了3次后缀自动机，放个板子在这里以免又忘。。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#define MAXN 100005
typedef long long LL;
struct SuffixAutomaton {
struct Node {
Node *link;
std::map<int, Node *> next;
int maxlen;
} * root, *last;
LL ans;
SuffixAutomaton() { last = root = new Node(); }
Node *add(int);
void build(int *, int);
} sam;
int N, a[MAXN], hash[MAXN], tot;
char gc();
LL read();
void print(LL);
void println(LL);
int main() {
N = read();
for (int i = 0; i < N; ++i)
a[i] = read();
sam.build(a, N);
}
inline char gc() {
static char buf[1000000], *p1, *p2;
if (p1 == p2) p1 = (p2 = buf) + fread(buf, 1, 1000000, stdin);
return p1 == p2 ? EOF : *p2++;
}
inline LL read() {
LL res = 0; char ch = gc();
while (ch < '0' || ch > '9') ch = gc();
while (ch >= '0' && ch <= '9')
res = (res << 1) + (res << 3) + ch - '0', ch = gc();
return res;
}
inline void print(LL x) {
static int buf[30];
if (!x) putchar('0');
else {
while (x) buf[++buf[0]] = x % 10, x /= 10;
while (buf[0]) putchar('0' + buf[buf[0]--]);
}
}
inline void println(LL x) { print(x); putchar('
'); }
SuffixAutomaton::Node *SuffixAutomaton::add(int c) {
Node *np = new Node(), *p = last;
np->maxlen = last->maxlen + 1;
while (p && !p->next.count(c)) p->next[c] = np, p = p->link;
if (!p) np->link = root;
else {
Node *q = p->next[c];
if (q->maxlen == p->maxlen + 1) np->link = q;
else {
Node *nq = new Node();
nq->link = q->link, nq->maxlen = p->maxlen + 1, nq->next = q->next;
q->link = np->link = nq;
while (p && p->next[c] == q) p->next[c] = nq, p = p->link;
}
}
return np;
}
void SuffixAutomaton::build(int *arr, int size) {
for (int i = 0; i < size; ++i) last = add(arr[i]), println(ans = ans + last->maxlen - last->link->maxlen);
}