Why this code received Runtime Error?

Revision en1, by kejpmdt, 2022-08-13 14:18:15
#include <bits/stdc++.h>
using namespace std;
void radixsort(vector<pair<pair<int, int>, int>> &a)
{
    int n = a.size();
    {
        vector<int> cnt(n);
        for (auto x : a)
        {
            cnt[x.first.second]++;
        }
        vector<pair<pair<int, int>, int>> a_new(n);
        vector<int> pos(n);
        pos[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for (auto x : a)
        {
            int i = x.first.second;
            a_new[pos[i]] = x;
            pos[i]++;
        }
        a = a_new;
    }
    {
        vector<int> cnt(n);
        for (auto x : a)
        {
            cnt[x.first.first]++;
        }
        vector<pair<pair<int, int>, int>> a_new(n);
        vector<int> pos(n);
        pos[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for (auto x : a)
        {
            int i = x.first.first;
            a_new[pos[i]] = x;
            pos[i]++;
        }
        a = a_new;
    }
}
int main()
{
    string s;
    cin >> s;
    s += "$";
    int n = s.size();
    vector<int> p(n), c(n);
    {
        vector<pair<char, int>> a(n);
        for (int i = 0; i < n; ++i)
        {
            a[i] = {s[i], i};
        }
        sort(a.begin(), a.end());
        for (int i = 0; i < n; ++i)
        {
            p[i] = a[i].second;
        }
        c[p[0]] = 0;
        for (int i = 1; i < n; ++i)
        {
            if (a[i].first == a[i - 1].first)
            {
                c[p[i]] = c[p[i - 1]];
            }
            else
            {
                c[p[i]] = c[p[i - 1]] + 1;
            }
        }
    }
    int k = 0;
    while ((1 << k) < n)
    {
        vector<pair<pair<int, int>, int>> a(n);
        for (int i = 0; i < n; ++i)
        {
            a[i] = {{c[i], c[(i + (1 << k)) % n]}, i};
        }
        radixsort(a);
        for (int i = 0; i < n; ++i)
        {
            p[i] = a[i].second;
        }
        c[p[0]] = 0;
        for (int i = 1; i < n; ++i)
        {
            if (a[i].first == a[i - 1].first)
            {
                c[p[i]] = c[p[i - 1]];
            }
            else
            {
                c[p[i]] = c[p[i - 1]] + 1;
            }
        }
        k++;
    }
    for (int i = 0; i < n; ++i)
    {
        cout << p[i] << ' ';
    }
    return 0;
}

All of the probable error will be in the function called radixsort ,the other part doesn't have any error.

Could anyone tell me where the error is?

The original code could be found in the Suffix Array of the edu.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English kejpmdt 2022-08-13 14:18:15 2808 Initial revision (published)