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;

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).

#include <bits/stdc++.h>

using namespace std;

ifstream cin("anagrame2.in");
ofstream cout("anagrame2.out");

char s[100001] , cuv[25000];
int f1[200] , f2[200];

bool egale()
{
    for(int i = 63 ; i <= 125 ; ++i)
        if(f1[i]!=f2[i])
            return 0;
    return 1;
}

int main()
{
    int c;
    cin >> c;
    cin >> s;
    cin >> cuv;
    if(c==2)
    {
        for(int j = 0 ; j < strlen(cuv) ; ++j)
            f1[(int)cuv[j]]++;
        for(int i = 0 ; i < strlen(cuv) ; ++i)
            f2[(int)s[i]]++;
        int cnt=0;
        int i = strlen(cuv);
        if(egale())
                cnt++;
        while(s[i]!='\0')
        {
            f2[(int)s[i-strlen(cuv)]]--;
            f2[(int)s[i]]++;
            if(egale())
                cnt++;
            i++;
        }
        cout << cnt;
    }
    else
    {
        for(int j = 0 ; j < strlen(cuv) ; ++j)
            f1[(int)cuv[j]]++;
        for(int i = 0 ; i < strlen(cuv) ; ++i)
            f2[(int)s[i]]++;
        int cnt=0;
        int i = strlen(cuv);
        if(egale())
                {
                    for(int j = i - strlen(cuv)+1 ; j < i+1 ; ++j)
                        cout << s[j];
                }
            else
        while(s[i]!='\0')
        {
            f2[(int)s[i-strlen(cuv)]]--;
            f2[(int)s[i]]++;
            if(egale())
                {
                    for(int j = i - strlen(cuv)+1 ; j <= i ; ++j)
                        cout << s[j];
                    break;
                }
            i++;
        }
    }
    return 0;
}