Сокращение отсортированного списка

Question

Предположим, у вас есть отсортированный список, содержащий имена серверов.Вы хотели бы свернуть их как можно плотнее.

Пример:

abcd01c, abcd02c, abcd04c, abcd05, z1x

должно стать

abcd0[1-4]c,abcd05,z1x

Какой самый простой алгоритм позаботиться о чем-токак это?

Answer 1

Я бы сохранил все строки в префиксной карте, что делает решение о существовании строки очень простым, а также позволяет быструю итерацию подмножества строк.

Хранить строки как:

(0)abcd01c
(5)     2c, 
(5)     4c, 
(4)    05, 
(0)z1x

Число - это количество символов, которое нужно взять из предыдущей строки. Это распространенная реализация для словарей, таких как телефонные книги, где вам нужно хранить много похожих строк.

A Trie - похожая структура, как Брайан Роуч заметил в комментариях.

Answer 2

Я немного неуверен в своих реальных потребностях, но подход к этому был бы в пользовательском Три (Википедия)

Когда вы достигли точки в вашемЕсли ваш следующий символ не является альфа-символом, вы будете знать, что у вас есть префикс.Внутри этого узла в Trie у вас может быть другая карта (не указывающая на дополнительные узлы Trie), которая снабжена суффиксом и содержит диапазоны для каждого.

Однако у вас все еще есть проблема с конкретными правилами, касающимися ваших данных.Если вы используете abcd01c в качестве ключа, будет ли префикс abcd или abcd0?

Answer 3

Я думаю, что динамическое программирование может помочь.Самая короткая длина может быть вычислена для всех наборов первых элементов данного массива, то есть {1}, {1,2}, {1,2,3} ... Эти числа вычисляются последовательно, поэтому для вычисления используются предыдущиетекущий номер.Если мы хотим вычислить A [i] и A [j] известны (j upd

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

int prevIdx = -1;
int count = 0;
for (int i = 1; i < list.Length; i++) {
    bool ok = true;
    if (list[i].Length == list[i - 1].Length) {
        int count = 0;
        for (int j = 0; j < list[i].Length; j++)
            if (list[i][j] != list[i - 1][j])
                curIdx = j;
                count++;
            }
        if (count > 1)
            ok = false;
    }
    else
        ok = false;
    if (ok) {
        if (prevIdx == curIdx) {
            count++;
        }
        else {
            prevIdx = curIdx;
            if (count > 1)
                answer.Add(list[i - 1].SubString(0, prevIdx - 1) + 
                    '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[i - 1].Length);
            else
                answer.Add(list[i - 1]);
            count = 0;
        }
    }
    else {
        if (count > 1)
            answer.Add(list[i - 1].SubString(0, prevIdx - 1) + 
                '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[i - 1].Length);
        else
            answer.Add(list[i - 1]);
        prevIdx = -1;
    }
}
if (count > 1)
    answer.Add(list[List.Length - 1].SubString(0, prevIdx - 1) + 
        '[' + count.ToString() + ']' + list[i - 1].SubString(prevIdx + 1, list[List.Length - 1].Length);
else
    answer.Add(list[list.Length - 1]);