Пусть вам даны две строки s и t, состоящие из латинских букв от a до f. Длины этих строк равны. Разрешено проводить над ними произвольное количество раз операцию вида: выбрать два различных символа c1 и c2 и заменить все вхождения символа c1 в обеих строках на c2. Определим расстояние между строками s и t, как минимальное количество раз, которое нужно применить операцию, чтобы строки стали равными. Например, если s равна abcd и t равна ddcb, расстояние между ними равно 2 — можно заменить все вхождения символа a на b, превратив s в bbcd и заменить все b на d, строки станут равны ddcd.
Вам даны две строки S и T. Для каждой подстроки S, состоящей из |T| символов, определите расстояние между этой подстрокой и T.
Первая строка содержит S, вторая — T (1 ≤ |T| ≤ |S| ≤ 125000). Обе строки состоят из строчных латинских букв от a до f.
Выведите |S| - |T| + 1 целых чисел. Число на позиции i должно равняться расстоянию между подстрокой S, начинающейся в позиции i, длины |T| и строкой T.
abcdefa
ddcb
2 3 3 3
Название |
---|