Re: подстроки

From

Oleg Khovayko ()

To

Dmitry Kitanin

Date

2003-01-18T01:25:09Z

Area

RU.ALGORITHMS

From: Oleg Khovayko <olegh@hotpop.com>

Dmitry Kitanin wrote:

> Меня интересовал алгоритм поиска для 1го символа с временем =const,не зависящим
> от длины строки в которой ищем. Такие алгоритмы вообще существуют? Или это в
> принципе не возможно? Предобработка меня не пугает.

Ну тогда заводишь массив из 256 integer-ов, делаешь один проход по
строке, и делаешь предобработку - складываешь в этот массив позицию
первого символа для всех симовлов:

statiс int *mas;

void pre_process(const char str) {
   unsigned const char *p;
   mas = malloc(0400 * sizeof(int));
   memset(mas, ~0, 0400);
   for(p = str; *p; p++)
     if(mas[*p] < 0) mas[*p] = p - str;
}


А потом делаешь поиск:

int char_pos(const unsigned char x) {
   return mas[x];
}

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

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)