Pagini recente » Cod sursa (job #1387456) | Cod sursa (job #415131) | Cod sursa (job #2453824) | Cod sursa (job #2772192) | Cod sursa (job #810912)
Cod sursa(job #810912)
#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;
}