Submission #1708131

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

//接尾辞配列を構成する(SA)
//高さ配列もついでに作る(LCP)
//LCPをセグ木にぶっこむとうれしいことが起きるらしい
struct SuffixArray {
	int n;
	string str;
	//sa[k]:=文字列[k,n)は辞書順で何番目か？
	vector<int>sa, lcp;
	//文字列sの接尾辞辞書を構成する O(n log n)
	SuffixArray(string s) :str(s), n(s.size()) {
		sa.resize(n + 1);
		vector<int>rank(n + 1);
		for (int i = 0; i <= n; ++i) {
			sa[i] = i;
			rank[i] = (i < n) ? str[i] : -1;
		}
		vector<int>tmp(n + 1);
		for (int k = 1; k <= n; k *= 2) {
			auto comp = [&](int i, int j) {
				if (rank[i] != rank[j])
					return rank[i] < rank[j];
				else {
					int ri = i + k <= n ? rank[i + k] : -1;
					int rj = j + k <= n ? rank[j + k] : -1;
					return ri < rj;
				}
			};
			sort(sa.begin(), sa.end(), comp);
			tmp[sa[0]] = 0;
			for (int i = 1; i <= n; ++i)
				tmp[sa[i]] = tmp[sa[i - 1]] + (comp(sa[i - 1], sa[i]) ? 1 : 0);
			rank = tmp;
		}
		//ここからLCP構築
		lcp.resize(n);
		for (int i = 0; i < n; ++i)rank[sa[i]] = i;
		int h = 0;
		lcp[0] = 0;
		for (int i = 0; i < n; ++i) {
			int j = sa[rank[i] - 1];
			if (h > 0)--h;
			for (; j + h < n&&i + h < n; ++h)
				if (str[j + h] != str[i + h])break;
			lcp[rank[i] - 1] = h;
		}
	}
};


int main(void)
{
	string s;
	cin >> s;
	SuffixArray sa(s);
	LL ans = 0;
	int N = s.size();
	for (int i = 0; i < N; ++i) {
		ans += (i + 1) * (N - i);
	}
	for (int i = 0; i < N; ++i) {
		LL p = sa.lcp[i];
		ans -= (p * (p + 1) / 2);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result