Rezolvare completă PbInfo #626 Anagrame2

Călin a primit de la învățătorul lui un exerciţiu pentru a-i testa atenția și rapiditatea. Având un șir de caractere, litere ale alfabetului englez și un cuvânt, Călin trebuie să afle care este prima anagramă (un cuvânt c1 este anagramă pentru alt cuvânt c2 dacă schimbând ordinea literelor lui c1 se obține c2) a cuvântului în șir și câte anagrame sunt. Călin, fiind pasionat de informatică dorește să rezolve această problemă printr-un program.

Cerința

Cunoscând șirul de caractere și cuvântul se cere:

a) să se afișeze prima anagramă a cuvântului în șir;
b) câte anagrame ale cuvântului sunt.

Date de intrare

Fişierul de intrare anagrame2.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află șirul de caractere, litere ale alfabetului englez. Pe următoarea linie se află cuvântul din enunț.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, în fişierul de ieşire anagrame2.out se va scrie prima anagramă a cuvântului în șir.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, în fișierul de ieșire anagrame.out se va scrie un număr natural reprezentând numărul de anagrame găsite în șir.

Restricții și precizări

  • 1 ≤ Lungime șir ≤ 100.000
  • 1 ≤ Lungime cuvânt ≤ 25.000
  • Există tot timpul cel puțin o anagramă a cuvântului în șir.
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

Exemplul 1:

anagrame2.in

1
anabnaacdRaanaSA
ana

anagrame2.out

ana

Explicație

p = 1

Prima anagramă a cuvântului în șir este ana.

Atenție! Pentru acest test se rezolvă doar cerința a).

Exemplul 2:

anagrame2.in

2
anabnaacdRaanaSA
ana

anagrame2.out

4

Explicație

p = 2

Sunt 4 anagrame ale cuvântului ana în șir: ana, naa, aan, ana.

Atenție! Pentru acest test se rezolvă doar cerința b).

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 Anagrame2:

#include <fstream>
#include <iostream>
#include<string.h>
#include<stdlib.h>
#define nmax 100001
using namespace std;

char s1[nmax],s[nmax];
int n,i,nr,m,p,a[26],A[26],c[26],C[26];
int anagrama(){
    int i;
    for(i=0;i<26;i++)
        if(a[i]!=c[i]||A[i]!=C[i])
            return 0;
    return 1;
}
int main()
{
    ifstream fin("anagrame2.in");
    ofstream fout("anagrame2.out");
    fin>>p;
    fin.get();
    fin.get(s,nmax,'\n');
    fin.get();
    fin.get(s1,nmax,'\n');
    fin.close();
    n=strlen(s1);
    m=strlen(s);
    nr=0;
    for(i=0;i<n;i++)
        if(s1[i]>='a'&&s1[i]<='z')
            a[s1[i]-'a']++;
        else
            A[s1[i]-'A']++;
    if(p==1){
        for(i=0;i<n;i++)
            if(s[i]>='a'&&s[i]<='z')
                c[s[i]-'a']++;
            else
                C[s[i]-'A']++;
        if(anagrama()){
            for(int j=0;j<n;j++)
                fout<<s[j];
            fout<<"\n";
            fout.close();
            return 0;
        }
        for(i=1;i<=m-n;i++){
            if(s[i-1]>='a'&&s[i-1]<='z')
                c[s[i-1]-'a']--;
            else
                C[s[i-1]-'A']--;
            if(s[i+n-1]>='a'&&s[i+n-1]<='z')
                c[s[i+n-1]-'a']++;
            else
                C[s[i+n-1]-'A']++;
            if(anagrama()){
                for(int j=i;j<=i+n-1;j++)
                    fout<<s[j];
                fout<<"\n";
                fout.close();
                return 0;
            }
        }
    }else{
        for(i=0;i<n;i++)
            if(s[i]>='a'&&s[i]<='z')
                c[s[i]-'a']++;
            else
                C[s[i]-'A']++;
        if(anagrama())
            nr++;
        for(i=1;i<=m-n;i++){
            if(s[i-1]>='a'&&s[i-1]<='z')
                c[s[i-1]-'a']--;
            else
                C[s[i-1]-'A']--;
            if(s[i+n-1]>='a'&&s[i+n-1]<='z')
                c[s[i+n-1]-'a']++;
            else
                C[s[i+n-1]-'A']++;
            if(anagrama())
                nr++;
        }
        fout<<nr<<'\n';

    }
    fout.close();
    return 0;
}

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 #626 Anagrame2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #626 Anagrame2 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!