Pagini recente » Profil motanzveri | Cod sursa (job #956574) | Cod sursa (job #2568144) | Cod sursa (job #1897376) | Cod sursa (job #810921)
Cod sursa(job #810921)
#include <fstream>
#include <cstring>
#define NMAX 2000004
#define Fact 73
#define Disp1 100007
#define Disp2 100021
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int Rez[NMAX],Nr;
char A[NMAX],S[NMAX];
int Hash1,Hash2,SHash1,SHash2;
void Contor(int p)
{
if(Nr>1000)return;
Nr++;
Rez[Nr] = p;
}
bool Verifica()
{
if(Hash1 == SHash1 && Hash2 == SHash2)
return 1;
return 0;
}
int main()
{
int N,M,i,F1 = 1,F2 = 1;
in>>A; N = strlen(A);
in>>S; M = strlen(S);
for(i=0;i<N;i++)
{
Hash1 = (Hash1*Fact+A[i])%Disp1;
Hash2 = (Hash2*Fact+A[i])%Disp2;
if(i)F1*=Fact,F1%=Disp1,F2*=Fact,F2%=Disp2;
}
for(i=0;i<N;i++)
{
SHash1 = (SHash1*Fact+S[i])%Disp1;
SHash2 = (SHash2*Fact+S[i])%Disp2;
}
if(Verifica())
Contor(0);
for(i=N;i<M;i++)
{
SHash1 = ((SHash1-(F1*S[i-N])%Disp1+Disp1)*Fact + S[i])%Disp1;
SHash2 = ((SHash2-(F2*S[i-N])%Disp2+Disp2)*Fact + S[i])%Disp2;
if(Verifica())
Contor(i-N+1);
}
out<<Nr<<'\n';
for(i=1;i<=Nr&&i<=1000;i++)
out<<Rez[i]<<' ';
return 0;
}