Rezolvare completă PbInfo #2464 anagrame3

Se dau două șiruri S1 si S2 formate doar cu litere mici. Numim subșir de lungime K al unui șir a un șir a' = ai1, ai2,…, aiK astfel încât să avem: i1 < i2 < ... < iK.

Cerința

Să se determine lungimea maximă a unui subșir din S1, format prin concatenarea unor anagrame ale șirului S2. Dintre toate subșirurile cu lungime maximă se va determina cel care este cel mai mic lexicografic. Un șir de lungime na se consideră mai mic lexicografic decât un șir de lungime nb dacă există un indice i, astfel încât a1=b1, a2=b1, …, ai-1=bi-1 și ai<bi. Un șir a este anagrama unui șir b dacă sortându-le crescător pe fiecare se obțin două șiruri identice.

Date de intrare

Fișierul de intrare anagrame3.in conține pe prima linie se află un număr natural P. Pe linia a doua se află șirul S1, iar pe a treia linie se află șirul S2.

Date de ieșire

În fișierul anagrame3.out, dacă P = 1, atunci pe prima linie se va scrie un număr natural reprezentând lungimea maximă a unui șir cu proprietatea cerută, iar dacă P = 2, atunci pe prima linie se va scrie subșirul de lungime maximă cu proprietatea cerută și minim lexicografic.

Restricții și precizări

  • 1 ≤ Lungime(S2) ≤ Lungime(S1) ≤ 100 000
  • Se garantează că cel puțin o anagramă a lui S2 apare în S1

Exemplul 1:

anagrame3.in

1
abbaaabababbaabaabba
aba

anagrame3.out

15

Explicație

Deoarece a apare de 11 ori, S2 poate să apară de cel mult 5 ori. Se observă subșirul format cu litere îngroșate și subliniate abbaaabababbaabaabba deci abaaabababaabaa este un subșir de lungime maximă, egală cu 15, cu proprietatea cerută.

Exemplul 2:

anagrame3.in

2
abbaaabababbaabaabba
aba

anagrame3.out

abaaabaabaabaab

Explicație

Se observă că subșirul verifică proprietatea cerută.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema anagrame3:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stack>

using namespace std;

int to_index(char c) {
    if (c >= 'a' && c <= 'z')
        return c - 'a';
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 26;
    assert(false);
}

int main() {
    ifstream cin("anagrame3.in");
    ofstream cout("anagrame3.out");

    int type; assert(cin >> type);
    string S, P; assert(cin >> S >> P);

    assert(1 <= S.size() && S.size() <= 1000 * 1000);
    assert(1 <= P.size() && P.size() <= S.size());

    for (auto &c : S)
        assert(('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z'));
    for (auto &c : P)
        assert(('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z'));

    vector<int> need(52, 0);
    for (auto &c : P)
        ++need[to_index(c)];

    int total = P.size();

    vector<int> where;
    for (int i = S.size() - 1; i >= 0; --i) {
        if (need[to_index(S[i])] > 0) {
            --need[to_index(S[i])];
            if (--total == 0) {
                where.push_back(i);
                total = P.size();
                for (auto &c : P)
                    ++need[to_index(c)];
            }
        }
    }

    if (type == 1) {
        cout << where.size() * P.size() << "\n";
        return 0;
    }

    reverse(where.begin(), where.end());
    where.push_back(S.size());
    where.erase(where.begin());

    int last = 0;
    for (auto &c : P)
        need[to_index(c)] = 0;

    vector<char> st;
    vector<int> have(52, 0);
    for (int i = 0; i < int(where.size()); ++i) {
        for (auto &c : P)
            have[to_index(c)] = need[to_index(c)] = 0;
        for (int j = last; j < where[i]; ++j)
            ++have[to_index(S[j])];
        for (auto &c : P)
            ++need[to_index(c)];

        st.clear();
        for (int j = last; j < where[i]; ++j) {
            if (!need[to_index(S[j])]) {
                --have[to_index(S[j])];
                continue;
            }

            // i need it, and its better
            while (!st.empty() && st.back() > S[j] && need[to_index(st.back())] < have[to_index(st.back())]) {
                need[to_index(st.back())]++;
                st.pop_back();
            }
            st.push_back(S[j]);

            need[to_index(st.back())]--;
            have[to_index(st.back())]--;
        }


        for (auto &c : st) {
            while (S[last] != c) {
                ++last;
            }
            ++last;
            cout << c;
        }
    }
    cout << "\n";
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2464 anagrame3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2464 anagrame3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!