/* Задача В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; }