SuffixArrayDiv1.cpp

#include <bits/stdc++.h>
using namespace std;

class SuffixArrayDiv1 {
    public:
        int minimalCharacters(vector<int> SA) {
            int n = SA.size();
            vector<int> pos(n + 1);
            vector<int> let(n);
            for (int i = 0; i < n; ++i) {
                pos[SA[i]] = i;
            }
            pos[n] = -1;
            let[SA[0]] = 1;
            for (int i = 1; i < n; ++i) {
                let[SA[i]] = let[SA[i - 1]];
                if (pos[SA[i - 1] + 1] > pos[SA[i] + 1]) let[SA[i]]++;
            }
            return let[SA[n - 1]];
        }
};