B. AB ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Вам даны две строки s и t, которые состоят из букв 'a' и 'b'. В строке s нет соседних одинаковых букв. Вы хотите выбрать наибольшее количество непересекающихся подпоследовательностей t, которые равны s. Подпоследовательность — это такая последовательность строки, которая может быть получена удалением нескольких (возможно ноль) элементов из этой строки. Найдите максимальное количество подпоследовательностей, которое вы сможете выбрать.

Входные данные
Первая строка входных данных содержит одну строку s (1≤|s|≤4). Гарантируется, что в строке s нет соседних одинаковых букв.

Вторая строка входных данных содержит одну строку t (1≤|t|≤105).

Выходные данные
Выведите одно целое число — максимальное количество подпоследовательностей, которое вы сможете выбрать.

Система оценки
Данная задача содержит 7 подзадач, в которых выполняются следующие ограничения:

Тесты из условия. Оценивается в 0 баллов.
|s|=1. Оценивается в 11 баллов.
|s|=2. Оценивается в 14 баллов.
|s|=3. Оценивается в 20 баллов.
|s|=4, |t|≤50. Оценивается в 18 баллов.
|s|=4, |t|≤300. Оценивается в 12 баллов.
|s|=4, |t|≤105. Оценивается в 25 баллов.
Примеры
входные данные
ab
abbaba
выходные данные
2
входные данные
aba
ababaa
выходные данные
2

Для решения задачи, необходимо понять, сколько раз строка $s$ может встретиться в строке $t$ как подпоследовательность. Подпоследовательность строки — это такая последовательность, которая может быть получена удалением некоторых (или всех) символов из строки $t$, сохраняя порядок оставшихся символов.

Разбор задачи

Важные моменты:

1. Длина строки $s$: так как $|s| \leq 4$, то $s$ может быть:

   • Длиной 1 (например, "a").
   • Длиной 2 (например, "ab").
   • Длиной 3 (например, "aba").
   • Длиной 4 (например, "abab").

2. Условие отсутствия одинаковых соседних букв в $s$: это упрощает задачу, так как подпоследовательности не могут иметь повторяющихся букв подряд. Например, $s = "aa"$ невозможно.

3. Цель задачи: найти максимально возможное количество таких непересекающихся вхождений $s$ в $t$.

Пример работы:

• Пример 1:
  Входные данные: $s = "ab"$, $t = "abbaba"$.
  Возможные подпоследовательности строки $t$, равные $s$:

  • Первое $"ab"$: позиции (1, 2).
  • Второе $"ab"$: позиции (4, 5).
    Ответ: 2 (максимальное количество таких непересекающихся вхождений).

• Пример 2:
  Входные данные: $s = "aba"$, $t = "ababaa"$.
  Возможные подпоследовательности строки $t$, равные $s$:

  • Первое $"aba"$: позиции (1, 2, 3).
  • Второе $"aba"$: позиции (4, 5, 6).
    Ответ: 2.

Алгоритм решения

1. Инициализация переменных:

   • Индекс для строки $t$ — $i$, который указывает текущую позицию в $t$.
   • Счетчик $count$, который будет содержать количество найденных вхождений $s$ в $t$.

2. Проход по строке $t$:

   • Для каждого символа $t[i]$, попробуем найти последовательность символов, совпадающую с $s$.
   • Используем два индекса: один для $t$ ($i$), второй для $s$ ($j$).
   • Если текущий символ $t[i]$ совпадает с текущим символом $s[j]$, то продвигаем $j$ на один шаг вперед. Если $j$ достиг конца строки $s$, то это означает, что мы нашли одну подпоследовательность $s$ в $t$, увеличиваем $count$ и обнуляем $j$.

3. Пропуск символов:

   • Если $j$ достиг конца $s$, обновляем $count$ и продолжаем поиск с текущей позиции $i$, чтобы найти следующую подпоследовательность.

4. Завершение:

   • Когда все символы $t$ обработаны, $count$ будет содержать ответ — максимальное количество таких подпоследовательностей.

Реализация

python
def max_subsequences(s, t):
    i, count = 0, 0  # Индекс в строке t и счетчик подпоследовательностей
    j = 0  # Индекс в строке s
    
    while i < len(t):
        if t[i] == s[j]:
            j += 1  # Совпадение символов, двигаем указатель по s
            if j == len(s):  # Если прошли всю строку s
                count += 1
                j = 0  # Сбрасываем указатель на начало s
        i += 1  # Всегда двигаем указатель по t
    
    return count
# Пример использования
print(max_subsequences("ab", "abbaba"))  # Вывод: 2
print(max_subsequences("aba", "ababaa"))  # Вывод: 2

Анализ сложности

• Временная сложность: $O(|t|)$. Мы проходим по строке $t$ один раз, проверяя каждый символ.
• Пространственная сложность: $O(1)$. Используются только переменные для хранения индексов и счетчика.

Вывод

Этот алгоритм позволяет эффективно определить максимальное количество непересекающихся подпоследовательностей $s$ в $t$, используя линейный проход по строке $t$.