Submission #3217848

---

Source Code Expand

# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, t, s, p, q, last, first, cnt, sum, ans, dp[200000];
Fll a[300000], b[300000];
string str, ss;
bool f;
char c, ch[100][100];
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
struct Edge { LL to, cost; };
vector<Edge>vec[200000];
vector<LL>v;
map<Fll, LL>ma;
multiset<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

struct SuffixArray{
	vector< int > SA, LCP;
	string s;
	void Build_SA(const string& str){
		s = str;
		SA.resize(s.size());
		iota(begin(SA), end(SA), 0);
		sort(begin(SA), end(SA), [&](const int& a, const int& b) {
			if (s[a] == s[b]) return (a > b);
			return (s[a] < s[b]);
		});
		vector< int > classes(s.size()), c(s.size()), cnt(s.size());
		for (int i = 0; i < s.size(); i++) {
			c[i] = s[i];
		}
		for (int len = 1; len < s.size(); len <<= 1) {
			for (int i = 0; i < s.size(); i++) {
				if (i > 0 && c[SA[i - 1]] == c[SA[i]] && SA[i - 1] + len < s.size() && c[SA[i - 1] + len / 2] == c[SA[i] + len / 2]) {
					classes[SA[i]] = classes[SA[i - 1]];
				}
				else {
					classes[SA[i]] = i;
				}
			}
			iota(begin(cnt), end(cnt), 0);
			copy(begin(SA), end(SA), begin(c));
			for (int i = 0; i < s.size(); i++) {
				int s1 = c[i] - len;
				if (s1 >= 0) SA[cnt[classes[s1]]++] = s1;
			}
			classes.swap(c);
		}
	}
	void Build_LCP(){
		vector< int > rank(s.size());
		for (int i = 0; i < s.size(); i++) {
			rank[SA[i]] = i;
		}
		LCP.resize(s.size() - 1);
		for (int i = 0, h = 0; i < s.size(); i++) {
			if (rank[i] + 1 < s.size()) {
				for (int j = SA[rank[i] + 1]; max(i, j) + h < s.length() && s[i + h] == s[j + h]; ++h);
				LCP[rank[i]] = h;
				if (h > 0) --h;
			}
		}
	}
	int operator[](int k) const{
		return (SA[k]);
	}
	int size() const	{
		return (s.size());
	}
	bool lt_substr(string& t, int si = 0, int ti = 0){
		int sn = s.size(), tn = t.size();
		while (si < sn && ti < tn) {
			if (s[si] < t[ti]) return (true);
			if (s[si] > t[ti]) return (false);
			++si, ++ti;
		}
		return (si >= sn && ti < tn);
	}
	int lower_bound(string& t){
		int low = -1, high = SA.size();
		while (high - low > 1) {
			int mid = (low + high) >> 1;
			if (lt_substr(t, SA[mid])) low = mid;
			else high = mid;
		}
		return (high);
	}
};


int main() {
	cin >> str;
	rep(i, str.size()) {
		ans += (str.size() - i)*(i + 1);
	}
	SuffixArray sa;
	sa.Build_SA(str);
	sa.Build_LCP();
	rep(i, str.size()-1) {
		ans-=sa.LCP[i]*(sa.LCP[i]+1)/2;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result