/*
Задача В3. СРЕЩАНЕ

Хората са любознателни същества. Обичат да задават какви ли не въпроси: “Какво
е искал да каже поетът написвайки това стихотворение?”, “Колко звезди се
виждат нощем на небето?”, “Дали зададено много голямо число е просто?”
и т.н. Разбира се, след това се опитват да отговарят на тези въпроси. Така, и
ние искаме да зададем един интересен въпрос, а вие да се опитате да отговорите
на него.

Нека P е мултимножество от N символа, т.е. не е задължително елементите на P да
са различни. Нека T е символен низ (текст), с дължина M. Казваме, че подниз на
T е съставен от елементите на P, ако всеки различен символ от подниза се съдържа
най-много толкова пъти в подниза, колкото пъти се съдържа в P. Например,
ако P=[“a”,“b”,“a”] и T=“xaaabayabaaz”, то поднизовете на Т “a” (7 на брой),
“b” (2 на брой), “ab” (2 на брой), “ba” (2 на брой), “aab” (1 на брой), “aba”
(2 на брой) и “baa” (1 на брой) са съставени от елементи на P, а всички други
поднизове на T не са съставени от елементи на P. Пита се колко е броят на
поднизовете на T с дължина N, които са съставени от елементите на P? Всеки от
символите на P и T е с ASCII код между 32 и 127 включително.

Напишете програма OCCUR.EXE, която по зададени мултимножество P и текст T намира
броя на поднизовете на T с дължина N, които са съставени от елементи на P.

Входните данни се четат от стандартния вход. Първият ред съдържа числата
N (1 <= N <= 100) и M (3 <= M <= 1 000 000), разделени с един интервал.
На втория ред има точно N символа – елементите на мултимножеството P. А на
третия ред, имащ точно М символа, е зададен текстът Т. 

Резултатът – търсеният брой поднизове – се извеждат на стандартния изход.



ПРИМЕР

Вход:
3 12
aba
xaaabayabaaz

Изход:
4



Решение на задача В3 – Срещане
От Иван Анев

Нека разгледаме поредица от N символа в текста T. Ако този подниз е съставен от
елементите на P то броят на а-та, b-та и т.н. ще е еднакъв. Тоест можем да
преброим за тази последователност от N символа броят на срещането на всяка
буква и да сравним дали съвпада със броят на всяка буква в P. Ако правим това
за всяка последователност от N символа ще сме решили задачата. За съжаление
директната реализация не би била достатъчно бърза.

Нека разгледаме каква е разликата в две последователности от N символа, които
започват съответно в позиция x и x+1. Разликата е само в първия и последния
символ. Тоест може чрез две операции – добавяне на нов краен символ и премахване
на стар начален символ - от броят на срещането на всяка буква в първата
последователност, да получим броят на срещането на буквите във втората.
Как да ускорим проверката дали срещането на буквите за някоя последователност от
N букви е еднакво със срещането на буквите в P. Може да броим броят на буквите,
на който срещането в двете множества се различава. И когато променяме срещането
на някоя буква да проверяваме дали срещането на тази буква в последователността
от N символа и множеството P от различно става еднакво, или от еднакво става
различно, или остава непроменено и в съответствие с това да променяме броят на
разликите в двете множества. Ако броят на разликите в даден момент е нула, това
означава, че конкретната последователност от N букви е съставена от буквите на P.

Метода, който се използва е известен като “метене”. Ние обхождаме текста от ляво
на дясно, като постоянно прибавяме най-предния символ и отстраняваме най-задния.
Реализацията на идеята е директно прилагане на идеята по-горе. Както лесно може
да се види скоростта е линейна по дължината на текста T.
*/



/*
NAME: Ivan Anev
PROG: occur
LANG: C
*/

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 100;
const int maxm = 1000000;
const int maxa = 26;

class Occur {
private:
        int n, m;
        char p[maxn], t[maxm];
public:
        void solve() {
                int ac[maxa];
                int i, d, x, c;

                cin >> n >> m >> p >> t;
                memset(ac, 0, sizeof(ac));
                for (i = 0; i < n; i++)
                        ac[p[i]-'a']++;
                d = 0;
                for (i = 0; i < maxa; i++)
                        if (ac[i] > 0)
                                d++;

                c = 0;
                for (i = 0; i < m; i++) {
                        x = t[i] - 'a';
                        ac[x]--;
                        if (ac[x] == 0)
                                d--;
                        else if (ac[x] == -1)
                                d++;

                        if (i - n >= 0) {
                                x = t[i-n] - 'a';
                                ac[x]++;
                                if (ac[x] == 0)
                                        d--;
                                else if (ac[x] == 1)
                                        d++;
                        }

                        if (d == 0)
                                c++;
                }

                cout << c << '\n';
        }
};

Occur occur;

int main() {
        occur.solve();

        return 0;
}