Submission #1608062

---

Source Code Expand

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

/*
thx
https://ideone.com/wZwOJq
https://www.slideshare.net/chokudai/square869120-contest2
*/
namespace suffix{
int N;//文字列の長さ
int doubles;//ソートするsuffixの文字幅
vector<int> rank;
vector<int> sa;
//(rank[i],rank[i+k])と(rank[j],rank[j+k])を比較
bool compare_sa(int i,int j){
	if( rank[i] != rank[j]){
		return rank[i] < rank[j];
	}else{
		int ri = i+doubles <= N ? rank[i+doubles]:-1;
		int rj = j+doubles <= N ? rank[j+doubles]:-1;
		return ri < rj;
	}
}

//ダブリングで構築していく
vector<int> construct(string S){
	//初期化
	N = S.size();
	vector<int> temp(N+1);
	sa.resize( N+1 );
	rank.resize( N+1 );//tempとrankは同じサイズ
	
	//最初の1文字,ランクは文字コードにすればよい
	for(int i=0;i<=N;++i){
		sa[i] = i;
		rank[i] = i<N ? S[i]:-1;//空文字は-1
	}
	
	//k文字についてソートされている所から
	//2k文字でソートする
	for(doubles=1; doubles <= N; doubles<<=1 ){
		sort(sa.begin(),sa.end(),compare_sa);

		//一旦tempに次のランクを計算し、
		//それからrankに移す
		temp[ sa[0] ] = 0;//空文字はいつでも先頭
		for(int i=1; i <= N; ++i){
			temp[ sa[i] ] = temp[ sa[i-1] ] +
				(compare_sa(sa[i-1],sa[i])?1:0);
		}
		rank = temp;
	}
	return sa;
}

}//namespace suffix

vector<int> LCP(string S,vector<int> SA){
	int lengths = S.size();

	vector<int> ret(lengths+1);
	vector<int> rank(lengths+1);//
	for(int i=0;i <= lengths;++i){
		rank[ SA[i] ] = i;
	}
	int h = 0;
	ret[0] = 0;
	for(int i=0;i<lengths;++i){
		int j = SA[rank[i]-1];
		if(h>0) h--;
		for(;j+h<lengths && i+h < lengths;++h){
			if( S[j+h] != S[i+h]) break;
		}
		ret[ rank[i]-1] = h;
	}
	return ret;
}

void solve(){
	string str;
	cin >> str;
	LL ret = 0;
	
	vector<int> v1 = suffix::construct(str);
	vector<int> v2 = LCP(str,v1);

	int size = str.size();
	for(int i=1;i<=size;++i){
		ret += 1ll * (size-v1[i])*(size-v1[i]+1)/2 -
			(LL)1*v2[i] * (v2[i]+1)/2;
	}
	cout << ret << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Submission Info

Judge Result