inlinevoidDA(ll m){ ll i, j, p; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[rnk[i]=s[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i-1]; for (i = n; i >= 1; i--) sa[sum[rnk[i]]--] = i; for (j = 1, p = 0; j <= n; j <<= 1, m = p) { p = 0; for (i = n - j + 1; i <= n; i++) sa2[++p] = i; for (i = 1; i <= n; i++) if (sa[i] > j) sa2[++p] = sa[i] - j; for (i = 1; i <= n; i++) key[i] = rnk[sa2[i]]; for (i = 1; i <= m; i++) sum[i] = 0; for (i = 1; i <= n; i++) sum[key[i]]++; for (i = 2; i <= m; i++) sum[i] += sum[i-1]; for (i = n; i >= 1; i--) sa[sum[key[i]]--] = sa2[i]; for (swap(rnk, sa2), p = 2, rnk[sa[1]] = 1, i = 2; i <= n; i++) { rnk[sa[i]] = check(sa2, sa[i-1], sa[i], j) ? p - 1 : p++; } } }
inlinevoidgeth(){ ll p = 0; for (ll i = 1; i <= n; i++) rnk[sa[i]] = i; for (ll i = 1; i <= n; i++) { if (p) p--; ll j = sa[rnk[i]-1]; while (s[i + p] == s[j + p]) p++; height[rnk[i]] = p; } }
intmain(){ scanf("%s", s+1); n = strlen(s+1); DA(128); geth(); stk[top=1] = 1; ans = 1ll * n * (n + 1) * (n - 1) / 2; for (ll i = 2; i <= n; i++) { while (top && height[stk[top]] > height[i]) top--; f[i] = f[stk[top]] + 1ll * (i - stk[top]) * height[i]; ans -= f[i] * 2; stk[++top] = i; } printf("%lld\n", ans); return0; }