HA_60_TS

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

pair<int,int> findAnagramSubstring(const string& T, const string& S) {
    if (S.size() > T.size()) return {-1, -1};

    vector<int> need(256, 0), window(256, 0);
    int distinct = 0; // число уникальных символов в S

    for (char c : S) {
        if (need[(unsigned char)c] == 0) distinct++;
        need[(unsigned char)c]++;
    }

    int matches = 0;
    auto add = [&](char c) {
        unsigned char uc = (unsigned char)c;
        window[uc]++;
        if (window[uc] == need[uc]) {
            matches++;
        } else if (window[uc] == need[uc] + 1) {
            // раньше было совпадение, теперь перестало
            matches--;
        }
    };

    auto remove = [&](char c) {
        unsigned char uc = (unsigned char)c;
        window[uc]--;
        if (window[uc] == need[uc]) {
            matches++;
        } else if (window[uc] + 1 == need[uc]) {
            // раньше не совпадало, теперь
            // перестало быть недостатком
            matches--;
        }
    };

    // Инициализация первого окна
    for (size_t i = 0; i < S.size(); ++i) {
        add(T[i]);
    }
    if (matches == distinct) {
        return {0, (int)S.size() - 1};
    }

    for (size_t i = S.size(); i < T.size(); ++i) {
        add(T[i]);
        remove(T[i - S.size()]);
        if (matches == distinct) {
            return {(int)(i - S.size() + 1), (int)i};
        }
    }

    return {-1, -1}; // не найдено
}

int main() {
    string T = "abacabatext";
    string S = "aabct";
    auto [l, r] = findAnagramSubstring(T, S);
    if (l != -1) {
        cout << "Found subarray: " << T.substr(l, r - l + 1) << " in indexes [" << l << ", " << r << "]\n";
    } else {
        cout << "There is now subarray\n";
    }
    return 0;
}