Проблема:
У Лайлы есть строка s из строчных английских букв, которую она повторяла бесконечно много раз.
Дано целое число n, найдите и выведите количество букв a в первых n буквах бесконечной строки Лайлы.
Например, если строка s = 'abcac' и n = 10, мы рассматриваем подстроку , abcacabcac первые 10 символов ее бесконечной строки. В подстроке есть 4 вхождения a.
Полную задачу читайте здесь: Повторяющаяся строка
Решение:
Предположим, что sub_str — это входная строка, а str_len — это длина бесконечной строки, которую мы рассматриваем.
Когда str_len меньше длины sub_str, мы можем легко вычислить количество a , перебирая строку.
Теперь, когда str_len больше, чем длина sub_str длины.
Во-первых, мы найдем количество подстрок ( sub_str) в рассматриваемой нами строке.
Во многих случаях размер комбинированных подстрок не кратен str_len, поэтому пропущено несколько символов, и эти символы могут содержать ' a '. Мы должны посчитать эти символы.
Теперь нам нужно найти количество a в sub_str. Пусть count будет хранить количество a в sub_str.
Умножение count на num_sub_str даст нам количество a в комбинированных подстроках, размер которых меньше или равен str_len и кратен размеру sub_str. Но осталось несколько символов, количество которых хранится в remaining_str_len. Мы должны найти вхождение '*a8' в эти символы и увеличить счетчик, если оно найдено.
Реализация C++ на Programmercave
Другие проблемы и решения соревновательного программирования
Первоначально опубликовано на https://programmercave0.github.io 24 апреля 2020 г.
