Pagini recente » Cod sursa (job #2864437) | Cod sursa (job #3203655) | Cod sursa (job #2987097) | Cod sursa (job #2449289) | Cod sursa (job #1675259)
#include<iostream>
#include<cstring>
#include<fstream>
using namespace std;
char poz[2000000];
int hashA1,hashA2,P1,P2,NA,NB,hashB1,hashB2,nr;
char A[2000009],B[2000009];
#define MOD1 100007
#define MOD2 100021
#define P 73
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
int main ()
{
fin.get(A,2000009);
fin.get();
fin.get(B,2000009);
NA=strlen(A);
NB=strlen(B);
if(NA>NB)
{
fout<<"0";
return 0;
}
P1=1;
P2=1;
hashA1=hashA2=hashB1=hashB2=0;
int i;
for(i=0;i<NA;i++)
{
hashA1=(hashA1*P+A[i])%MOD1;
hashA2=(hashA2*P+A[i])%MOD2;
if(i!=0)
{
P1=(P1*P)%MOD1;
P2=(P2*P)%MOD2;
}
}
for(i=0;i<NA;i++)
{
hashB1=(hashB1*P+B[i])%MOD1;
hashB2=(hashB2*P+B[i])%MOD2;
if(hashA1==hashB1 && hashA2==hashB1)
{
nr++;
poz[0]=1;
}
}
for(i=NA;i<NB;i++)
{
hashB1=((hashB1- (P1 * B[i-NA]) %MOD1 +MOD1) *P+ B[i])%MOD1;
hashB2=((hashB2- (P2 * B[i-NA]) %MOD2 +MOD2) *P+ B[i])%MOD2;
if(hashA1==hashB1 && hashA2==hashB2)
{
nr++;
poz[i-NA+1]++;
}
}
fout<<nr<<endl;
int x=0;
for(i=1; i<NB && x<1000 ; i++)
{
if(poz[i])
{
fout<<i<<" ";
x++;
}
}
fin.close();
fout.close();
return 0;
}