Олимпиадный тренинг

Задача . F. Подстроки в строке


Задача

Темы: битмаски Перебор Строки строковые суфф. структуры Структуры данных *3000

Дана строка s, обработайте q запросов, каждый из которых имеет один из следующий типов:

  • 1 i c — Изменить i-й символ в строке на c.
  • 2 l r y — Рассмотрим подстроку строки s, начинающуюся с символа с номером l и заканчивающуюся на символ с номером r. Выведите количество раз, которые y входит в неё как подстрока.
Входные данные

В первой строке задана строка s (1 ≤ |s| ≤ 105), состоящая из строчных букв английского алфавита.

Во второй строке задано число q (1 ≤ q ≤ 105) — количество запросов.

Следующие q строк описывают запросы и могт в зависимости от типа запроса имеють следующие форматы:

  • 1 i c (1 ≤ i ≤ |s|)
  • 2 l r y (1 ≤ l ≤ r ≤ |s|)

c — это строчная буква английского алфавита, y — непустая строка, состоящая из строчных букв английского алфавита.

Сумма |y| по всем запросам второго типа не превосходит 105.

Гарантируется, что в тесте есть хотя бы один запрос второго типа.

Строки индексируются, начиная с 1.

|s| обозначает длину строки s.

Выходные данные

Для каждого запроса типа 2 выведите ответ в отдельной строке.

Примечание

В первом тестовом примере изначально строка aba встречается 3 раза как подстрока на подотрезке [1, 7].

После запроса первого типа строка становится равной ababcbaba и строка aba встречается только один раз как подстрока на отрезке [1, 7].


Примеры
№Входные данныеВыходные данные
1 ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba 
3
1
2 abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa 
2
2
1

time 6000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет