Skip to content

enchained/hh_inf_sequence

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 

Repository files navigation

2. Бесконечная последовательность

Возьмём бесконечную цифровую последовательность, образованную склеиванием последовательных положительных чисел: S = 123456789101112131415... Определите первое вхождение заданной последовательности A в бесконечной последовательности S (нумерация начинается с 1).

Пример входных данных:
6789
111

Пример выходных данных:
6
12

Запуск программы:

python inf_sequence.py 111

Пример результата:

>>>
Input 111 positioned at 12

Запуск тестов:

python inf_sequence_test.py -v

Тесты проводятся на примере из задания, также сравниваются результаты брутфорс- и KMP-решения для случайной последовательности.

Пример вывода:

>>>
test111_from_example (__main__.PosInSeqTests) ... ok
test6789_from_example (__main__.PosInSeqTests) ... ok
test_kmp (__main__.PosInSeqTests) ... ok

----------------------------------------------------------------------
Ran 3 tests in 2.367s

OK

Ранняя брутфорс-версия решения являлась крайне неэффективной на определенных наборах данных, так как время работы алгоритма сильно зависит от глубины первого вхождения, ведь сложность алгоритма - O(A*S). Для оптимизации было принято решение использовать алгоритм Кнута-Морриса-Пратта. Сложность данного алгоритма всего лишь O(A+S).

За основу было взята реализация алгоритма из книги Python Cookbook (O'Reilly) - recipe 5.13. Finding Subsequences. Данная реализация позволяет использовать в качестве последовательности S произвольный итератор.

Были произведены следующие модификации:

  • Поскольку нас интересует лишь первое вхождение подстроки, генератор вхождений был заменен на возврат позиции.
  • Вместо посимвольного перебора конечного текста был использован генератор, проходящий по символам последовательных целых чисел.
  • Так как исчисление позиции в задании идет с 1, а не с 0, возвращаемая позиция была увеличена на 1.

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages