Submission #1512474

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <set>
#include <iomanip>
#include <deque>
#include <stdio.h>
#include <random>
using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;

class SuffixArray {
    
private:
    
    int N,k;
    string S;
    vector< int > rank_sa, tmp, sa;
    
    void build_suffix_array() {
        rank_sa.resize(N + 1), tmp.resize(N + 1), sa.resize(N + 1);
        auto compare_sa = [&] (int i, int j) -> bool {
            if (rank_sa[i] != rank_sa[j]) {
                return rank_sa[i] < rank_sa[j];
            } else {
                int ri = i + k <= N ? rank_sa[i + k] : -1;
                int rj = j + k <= N ? rank_sa[j + k] : -1;
                return ri < rj;
            }
        };
        for (int i = 0; i <= N; i++) {
            sa[i] = i;
            rank_sa[i] = i < N ? S[i] : -1;
        }
        for (k = 1; k <= N; k <<= 1) {
            sort(sa.begin(), sa.end(), compare_sa);
            tmp[sa[0]] = 0;
            for (int i = 0; i <= N; i++) {
                tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
            }
            for (int i = 0; i <= N; i++) {
                rank_sa[i] = tmp[i];
            }
        }
    }
    
    vector< int > rank_lcp;
    vector< int > lcp;
    
    void build_lcp() {
        rank_lcp.resize(N + 1), lcp.resize(N + 1, 0);
        for (int i = 0; i <= N; i++) {
            rank_lcp[sa[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < N; i++) {
            int j = sa[rank_lcp[i] - 1];
            if (h > 0) h--;
            while (j + h < N && i + h < N) {
                if (S[j + h] != S[i + h]) break;
                h++;
            }
            lcp[rank_lcp[i] - 1] = h;
        }
    }
    
public:
    
    SuffixArray (string s) : S(s), N((int)s.size()) {
        build_suffix_array();
        build_lcp();
    }
    
    int get_lcp(int idx) {
        return lcp[idx];
    }
    
    int get_rank(int idx) {
        return rank_sa[idx];
    }
    
    int operator [] (int idx) {
        return sa[idx];
    }
    
};


int main() {
    
    
    string s; cin >> s;
    SuffixArray inst(s);
    
    ll ans = 0;
    REP(i,s.size()) {
        ll len = (int)s.size() - inst[i + 1];
        ans += len * (len + 1) / 2 - inst.get_lcp(i) * (inst.get_lcp(i) + 1) / 2;
    }
    
    cout << ans << endl;
    
    return 0;
}

Submission Info

Judge Result