Алфавитное разделение индексов подстрок в выпусках C ++ - PullRequest
Новая
       4

Алфавитное разделение индексов подстрок в выпусках C ++

0 голосов
/ 10 февраля 2020

Некоторое время назад я пытался заставить этот код работать для разбиения (как при подготовке к быстрой сортировке) индексов суффиксов подстрок, и пока он близок, я не получаю то, что ожидаю. Мне было интересно, может ли помочь набор sh глаз. 

int partition(const string &S, vector<int> &indices, int low, int high, int pivotIndex)
{
    int i = low;
    int j = high - 1;
    swap(indices[high], indices[pivotIndex]);
    while (i <= j)
    {
        while (i < high && !lessThan(S, S[i], S[indices[high]]))
            i++;
        while (j >= low && lessThan(S, S[j], S[indices[high]]))
            j--;
        if (i < j)
        {
            int temp = indices[i];
            indices[i] = indices[j];
            indices[j] = temp;
            i++;
            j--;
        }
    }
    swap(indices[high], indices[i]);
    return i;
}

Индексы - это просто вектор размером 0, 1, 2, ..., n того же размера, что и строка S.

А вот программа, которую я написал для lessThan, просто чтобы вы знаю, с чем я работаю: 

bool lessThan(const string &S, int first, int second)
{

    int counter = (int)S.length() - ((first <= second) ? second : first);
    for (int i = 0; i <= counter; ++i)
    {
        if (S[first + i] != S[second + i])
        {
            if (S[first + i] < S[second + i])
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    if (first < second)
    {
        return false;
    }
    else
    {
        return true;
    }
}

less. Кажется, что он работает нормально, когда я тестирую его отдельно, поэтому я не думаю, что это проблема, но, возможно, это так.

Всякий раз, когда я проверяю, скажем, строку "abracadabra" и устанавливая pivotIndex в 4, я ожидаю получить "0 1 8 3 10 5 7 4 2 9 6" в качестве выходных данных, но вместо этого получаю " 0 1 8 3 7 5 4 10 2 9 6 ". Близко, но не совсем. Кто-нибудь может определить мою ошибку?

(PS Я знаю, что, возможно, мог бы использовать substr () или какое-то другое решение, чтобы сделать меньше, чем проще, но я пытаюсь сделать это без выделения дополнительной памяти, я сосредоточен на функции разделения)

редактировать: я понял это. Полная ошибка на моей стороне. Проверьте ниже для ответа

1 Ответ

1 голос
/ 10 февраля 2020

Я был идиотом, вход в lessThan должен был получить два дюйма. Я вместо этого дал ему два символа от S. Также поменялся, который меньше, чем называют! Был на. Я думаю, что я просто слишком поздно запрограммировал и обвиняю всех в лишении сна.

Фиксированный код: 

int partition(const string &S, vector<int> &indices, int low, int high, int pivotIndex)
{
    int i = low;
    int j = high - 1;
    swap(indices[high], indices[pivotIndex]);
    while (i <= j)
    {                                   //This right here
        while (i < high && lessThan(S, indices[i], indices[high]))
            i++;
        while (j >= low && !lessThan(S, indices[j], indices[high]))
            j--;
        if (i < j)
        {
            swap(indices[i], indices[j]);
            i++;
            j--;
        }
    }
    swap(indices[high], indices[i]);
    return i;
}
...