Cod sursa(job #810912)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 11 noiembrie 2012 11:49:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>
#define NMAX 2000004

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const unsigned int CodeKey = 32749;
const unsigned int SCodeKey = 1;//666013;

unsigned int  KeyExt, KeyXor, KeyAsc;
unsigned int SKeyExt,SKeyXor,SKeyAsc;

int Rez[1004],Nr,Sum;
char A[NMAX],S[NMAX];

inline unsigned int Code(int nr){ return nr * CodeKey;}
inline unsigned int SCode(int nr){ return nr * SCodeKey;}

void Contor(int p)
{
    if(Nr>1000)return;
    Nr++;
    Rez[Nr] = p;
}

bool Verifica()
{
    if(KeyXor==SKeyXor && KeyAsc == SKeyAsc && KeyExt == SKeyExt)
        return 1;
    return 0;
}

int main()
{
    int N,M,i;
    in>>A;    N = strlen(A);
    in>>S;    M = strlen(S);

    for(i=0;i<N;i++)
        KeyXor^=Code(A[i]),KeyExt+=(N-i)*SCode(A[i]);

    for(i=0;i<N;i++)
        SKeyXor ^=Code(S[i]),SKeyExt+=(N-i)*SCode(S[i]),Sum+=SCode(S[i]);
    if(Verifica())
        Contor(0);

    for(i=N;i<M;i++)
    {
        SKeyXor^= Code(S[i-N]),SKeyXor^= Code(S[i]);
        Sum-=SCode(S[i-N]);Sum+=SCode(S[i]);
        SKeyExt+= SCode(Sum) - N*SCode(S[i-N]);
        if(Verifica())
            Contor(i-N+1);
    }
    out<<Nr<<'\n';
    for(i=1;i<=Nr&&i<=1000;i++)
        out<<Rez[i]<<' ';
    return 0;
}