Pagini recente » Cod sursa (job #503074) | Cod sursa (job #2969090) | Cod sursa (job #546468) | Cod sursa (job #3220705) | Cod sursa (job #810926)
Cod sursa(job #810926)
#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[1004],Nr;
char A[NMAX],S[NMAX];
int Hash1,Hash2,SHash1,SHash2;
void Contor(int p)
{
Nr++;
if(Nr>1000)return;
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);
if(N>M)
{
out<<"0\n";
return 0;
}
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;
}