VPF::[Алгоритм] Разбиение строки - Форум программистов

ShavarRsh

Дата 12.9.2011, 23:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

Всем привет!
Вот такая задачка: есть строка. Надо ее разбить на подстроки одинаковой длины (длина задана), причем чтобы каждая подстрока начиналась с префикса [x\y] где x - номер подстроки, а y - общее количество подстрок.

Например, исходная строка: "In the beginner's mind there are many possibilities, but in the expert's there are few." Пусть длина подстроки 20, тогда в результате получим следующие подстроки:

"[1\6]In the beginner"
"[2\6]'s mind there a"
"[3\6]re many possibi"
"[4\6]lities, but in "
"[5\6]the expert's th"
"[6\6]ere are few."

Заметьте, что размер "In the beginner" равен 15, т.к. 5 символов занимает префикс "[1\6]".
Сложность в том, что при увеличении размера исходной строки, префикс будет расти, оставляя меньшее количество символов, которые могут поместиться в оставшуюся часть подстроки. Т.е. если бы нам понадобилось 10 подстрок, то размер префикса был бы равен 6 для первых 9-и подстрок и 7 для последней.

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

Естественно, вариант простого перебора smile

(когда мы просто делаем предположение о количестве подстрок, а если не помеситлось - увеличиваем и проверяем снова) - не самое красивое решение smile

Заранее спаибо за участие smile

Это сообщение отредактировал(а) ShavarRsh - 12.9.2011, 23:21

volatile

Дата 13.9.2011, 02:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85

Цитата(ShavarRsh @ 12.9.2011, 23:06

)

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

Код


int substring_count ( int str_size, int sub_size )
{
   int max = 0, dec = 0, prev = 0;
   int i = sub_size - 3;
   do
   {
      if ( i <= 2 ) return 0;
      i -= 2;
      dec = dec * 10 + ! dec;
      prev = max - dec + 1;
      max = prev + i * dec * 9;
   } while ( max < str_size );

   return dec - 1 + ( str_size - prev + i - 1 ) / i;
}

Цикл выполняется быстро. Не более log10(N) раз.
т.е например, для строки размером 1000000 (мульон) символов, не более 6 раз.

При невозможности разбиения, возвращает 0

Проверить на разные значения можете здесь:
http://liveworkspace.org/code/fd164556eb57...61aeb62611e7dc1

Проверяйте!
smile

volatile

Дата 13.9.2011, 10:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 8
Всего: 85

Вчера ночью не заметил:

Цитата(volatile @ 13.9.2011, 02:40

)

return dec - 1 + ( str_size - prev + i - 1 ) / i;

Последний ретурн можно слегка сократить:

Код


   return dec + ( str_size - prev - 1 ) / i;

Впрочем, это не ошибка.

ShavarRsh

Дата 13.9.2011, 17:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

Круто! Большое спасибо!

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »