Понимание конечного значения в алгоритме сжатия потока

Question

Что должно произойти с окончательным значением эксклюзивного сканирования в алгоритме сжатия потока?

Это пример для выбора всех символов "А".

Последовательность А:

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3

0 - A
1 - A
2 - A
3 - A

Последовательность B (такая же, кроме последнего значения):

Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3

0 - A
1 - A
2 - A
3 - B

Очевидно, что второй пример дает неверный конечный результат, основанный на выполнении наивного цикла по значениям сканирования, записываемым в эти адреса.

Что мне здесь не хватает?

Обновить:

Как я понимаю алгоритм сканирования, я бы сделал эквивалент следующего:

for (int i = 0; i < scan.length(); i++)
{
    result[scan[i]] = input[i];
}

Параллельно это будет связано с инструкцией разброса.

Answer 1

После A вы предполагаете, что будет хотя бы еще один A. Поэтому вы полагаете, что последовательность заканчивается буквой A. Если это не так, вы выбираете неверную последнюю букву.

Вам просто нужно посчитать как. Не начинайте с 1. Начните с 0. Увеличивайте этот счет только тогда, когда вы найдете A.

Или... Обновление:

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3 4
                             ^
0 - A                        |
1 - A                        Four elements
2 - A
3 - A


Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3 3
                             ^
0 - A                        |
1 - A                        Three elements
2 - A