Нахождение предыдущего вхождения в массив.

[BanmaN]

Добрый день.

Хочется найти быстрое решение задачи: дан массив $A$ длины $n$ символов, требуется построить массив чисел $B$ , такой что на $i$-ой позиции массива $B$ стоит число $x$ тогда и только тогда, когда $A[x] = A[i]$ или $x = -1$ и число x максимальное с таким свойством из тех, что $< i$, притом для одинаковых символов из массива A должна быть ровно одна позиция $B$, где стоит единица (т.е. при первом появлении символа в массиве A). Пример: массив $A : a, b, c, d, c, c, a$; массив $B: -1, -1, -1, -1, 2, 4, 0$.

Решение есть и даже за $O(n)$, но хочется попроще.
Составить хэш таблицу $H$ символов, изначально в каждой ячейке которой поместить $-1$. После поочерёдно пробежаться по массиву $A$ и выполнить операцию: на $i$-ом шаге в $B[i]$ вписать $H[A[i]]$ и заменить $H[A[i]]$ на $i$.

Меня именно не устраивает в этом решении использование хэш функции. Задача очень естесственная и уже несколько раз встречалась на практике. Понятно, за ассимптотикой некуда гнаться, хочется за константой.

Заранее спасибо за Ваши советы.

P.S.: Понятно, что тут можно под каждый символ создать массив, там всего будет 24 ячейки - не велика потеря, но изначально задача стоит так, что и в первом массиве - числа.

[gris]

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

[BanmaN]

Размер массива может быть очень большим, $4 000 000 000$ может быть легко. Количество же различных чисел где-то $10000$. Однако хотелось бы полегче что-нибудь концептуально.

Одно из применений связано с поиском подстроки во многих документах и вывод всех документов, содержащих подстроку (алг. работает за $k + l$, где $k$ - количество документов, в которых слово лежит, $l$ - длина слова), другое применение - c алгоритмом кэширования furthest-in-future [CLRS страница 449 в 3-ем издании].

[Pavia]

Диапазон значений чисел А[i] известен?
Если памяти хватает то просто массив заводим вместо хэша используем само число.
О(n). Хэши это естественно и ими легко пользоваться, да и быстрее не будет. Можно деревья использовать будет O(n*log (m)) m - число различных цифр. Более медленно это делать просто массив и добавлять в него новые числа. O(n*m) Можно и медленнее вот только обычно все ищут как быстрее а вы почемуто как медленнее.