• Haskell специальная_олимпиада Есть у нас строка. Приблизительно такая STIEEQAKTFLDKFNHEAEDLFYQSSLASWNYNTNITEENVQNMNNAGDKWSAFLKEQSTLAQMYPLQEI. Нам нужно сформировать список всех уникальных подстрок этой строки. Ну то есть nub . subsequences, но так чтобы на ноутбуке с 16 гигабайтами памяти завершалось хотя бы за минуту. Считать строку массивом байтов — нельзя.

Replies (12)

  • @ndtimofeev, на неигрушенчном языке тоже по условиям писать нельзя, да?
  • @ndtimofeev, кстати, а TESAQ — подстрока это строки или нет?
  • @glupovat, Конечно.
  • @glupovat, Ну давай на неигрушечном.
  • @ndtimofeev, А массивом чего считать строку? Какие нибудь уникодные извраты, нормировки, collation, прочее надо учитывать?
  • @max630, Не… Никакого юникода. Строка состоит из символов. Они могут быть представлены одним Char'ом, могут быть представлены строкой, могут быть представлены ссылкой на запись в таблице. А работать нужно вне зависимости от представления. Это к слову сиквенс пептида.
  • @ndtimofeev, Что-то 2^70 много как-то, думать придётся.
  • @glupovat, Почему так много, по-моему length^2 всего подстрок должно быть
  • @glupovat, Да, похоже я охуел.
  • @ndtimofeev, s/nub/nubOrd
  • @max630, Я потому про подстроку из отдельных несоседних символов и спросил.
  • @max630, Эээ… Нет. У меня есть строка которую я набиваю на клавиатуре. Иногда я пропускаю нажатие кнопки. Проверить что я набрал я не могу. Зато могу суммировать все символы в строке и если сумма совпадает, то я набрал то что нужно. Но иногда сумма отличается и я хочу понять какую кнопку я не нажал. Для этого мне нужно прикинуть какой строке может соответствовать эта сумма.