Алгоритм подсчета идентичных мультимножеств символов

Question

Я ищу быстрый (фактическое время, а не асимптотический c сложность) алгоритм для подсчета идентичных мультимножеств символов. Например, вход

BCDEFGH
ABACD
BDCEF
BDCAA
DBACA
DABACA
DABAC
BCDEHFG

имеет 4 идентичных набора, а именно

ABACD
BDCAA
DBACA
DABAC

и еще 2 идентичных набора

BCDEFGH
BCDEHFG

Наборы могут быть большими ( > 10000 символов)

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

В качестве альтернативы, есть ли другие алгоритмы, которые могут работать лучше на практике? Пожалуйста, также дайте мне знать о любых подсказках и приемах ускорения

Answer 1

Для уменьшенного алфавита, как вы демонстрируете в своем примере, вы можете использовать массив short[8] и подсчитывать в этом массиве все присутствие символов в наборе. После этого, ха sh этот массив. Смотрите следующий пример:

uint16_t arr[8];

bzero(arr, siezeof(arr)); // clear array before usage

for(int i = 0; i < setline.size(); i++) // fill swap-independent arr, O(N)
    arr[setline[i] - 'A']++;

// Hash the array
uint32_t h = 0xDEADBEEF;
for(int i = 0; i < 8; i++)
    h = ((h << 11) | (h >> (32 - 11))) + arr[i];