Cod sursa(job #2279815)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 10 noiembrie 2018 00:26:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>

#include <cstring>

#include <cstdlib>

using namespace std;

ifstream fin("strmatch.in");

ofstream fout("strmatch.out");

char A[2000005],B[2000005],y;

int nA,nB,i,j,fA[300],fB[300],mA,mB,xmin,z[1002],nr,ok;

int main()

{

    fin>>A>>B;

    nA=0;mA=0;

    while(A[nA]){

        fA[(int)A[nA]]++;

        if(fA[(int)A[nA]]==1)mA++;

        nA++;

    }



    mB=0;ok=1;nr=0;

    for(i=0;i<nA;i++){

        fB[(int)B[i]]++;

        if(fB[(int)B[i]]==fA[(int)B[i]])mB++;

        else if(fB[(int)B[i]]==1+fA[(int)B[i]])mB--;

        if(B[i]!=A[i])ok=0;

    }

    if(ok==1){

        nr++;

        if(nr<=1000){

            z[nr]=0;

        }

    }

    for(i=nA;B[i]!=0;i++){

        fB[(int)B[i-nA]]--;

        if(fB[(int)B[i-nA]]==fA[(int)B[i-nA]]-1) mB--;

        else if(fB[(int)B[i-nA]]==fA[(int)B[i-nA]]) mB++;

        fB[(int)B[i]]++;

        if(fB[(int)B[i]]==fA[(int)B[i]])mB++;

        else if(fB[(int)B[i]]==1+fA[(int)B[i]])mB--;
        if(mA==mB){

            ok=1;

            for(j=0;j<nA;j++){

                if(A[j]!=B[i-nA+1+j]){

                    ok=0;break;

                }

            }

            if(ok==1 && mB==mA){

                nr++;

                if(nr<=1000){

                    z[nr]=i-nA+1;

                }

            }
        }

    }

    fout<<nr<<"\n";

    for(i=1;i<=nr && i<=1000;i++){

        fout<<z[i]<<" ";

    }

    fout.close();

    fin.close();

    return 0;

}