suffix array, lcp

#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <memory.h>
#include <algorithm>
#include <stack>
#include <deque>
#include <iomanip>
#include <stdio.h>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <iterator>
#include <chrono>
#include <array>
#include <bitset>
#define pii pair <long long, long long>
#define debug(x) cerr << (#x) << " " << (x) << endl
#define pb push_back
#define all(vc) vc.begin(), vc.end()
#define endl "\n"
using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const long long ABC = 300;

void suffix_array(string& s, vector<int>& p, vector<int>& c, vector<int>& lcp) {
    s += "$";
    int n = (int)(s.size());
    p.resize(n);
    c.resize(n);
    vector<int> cnt(ABC);
    for (int i = 0; i < n; i++) {
        cnt[s[i]]++;
    }
    for (int i = 1; i < ABC; i++) {
        cnt[i] += cnt[i - 1];
    }
    for (int i = 0; i < n; i++) {
        p[--cnt[s[i]]] = i;
    }
    c[p[0]] = 0;
    int cls = 1;
    for (int i = 1; i < n; i++) {
        c[p[i]] = c[p[i - 1]];
        if (s[p[i]] != s[p[i - 1]]) {
            c[p[i]]++;
            cls++;
        }
    }
    vector<int> pn(n);
    for (int k = 0; (1LL << k) < n; k++) {
        for (int i = 0; i < n; i++) {
            pn[i] = (n + p[i] - (1 << k)) % n;
        }
        cnt.assign(cls, 0);
        for (int i = 0; i < n; i++) {
            cnt[c[pn[i]]]++;
        }
        for (int i = 1; i < cls; i++) {
            cnt[i] += cnt[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            p[--cnt[c[pn[i]]]] = pn[i];
        }
        vector<int> cn(n);
        cn[p[0]] = 0;
        int clss = 0;
        for (int i = 1; i < n; i++) {
            cn[p[i]] = cn[p[i - 1]];
            pii a = { c[p[i]], c[(p[i] + (1LL << k)) % n] };
            pii b = { c[p[i - 1]], c[(p[i - 1] + (1LL << k)) % n] };
            if (a != b) {
                cn[p[i]]++;
                clss++;
            }
        }
        cls = clss + 1;
        c.swap(cn);
    }
    lcp.resize(n);
    int l = 0;
    for (int i = 0; i < n; i++) {
        if (c[i] == n - 1) {
            continue;
        }
        int nxt = p[c[i] + 1];
        while (max(i, nxt) + l < n && s[i + l] == s[nxt + l]) {
            l++;
        }
        lcp[c[i]] = l;
        l = max(0, l - 1);
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    cout.precision(17);

    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> p(n), c, lcp;
    for (int &i : p) {
        cin >> i;
    }
    suffix_array(s, p, c, lcp);
    for (int i = 1; i < (int)(p.size()) - 1; i++) {
        cout << lcp[i] << endl;
    }
    return 0;
}