Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя kejpmdt

Автор kejpmdt, история, 2 года назад, По-английски
#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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
for (int i = 1; i <= n; ++i)
{
    pos[i] = pos[i - 1] + cnt[i - 1];
}

One mistake i found was this:

Here size of pos is only $$$n$$$ so you cannot access $$$pos_n$$$