Pagini recente » Cod sursa (job #2642034) | Cod sursa (job #116899) | Cod sursa (job #2892042) | Cod sursa (job #642273) | Cod sursa (job #1527840)
#include <fstream>
#include <cstring>
#define M1 100129
#define M2 101111
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
int v[1000];
int powr(int baza,int putere)
{
int r=1;
while(putere>1)
{
if(putere%2==0)
{
putere>>=1;
baza=(baza*baza)%M1;
}
else
{
putere--;
r=(r*baza)%M1;
}
}
return (baza*r)%M1;
}
int main()
{
int hashA=0,hashB=0,nr=0,hashA2=0,hashB2=0;
f.getline(a,2000001);
f.getline(b,2000001);
int length=strlen(a);
int power=length-1;
int powermax=powr(256,power);
int rr=1;
for(int i=0;i<length;i++)
{
hashA=(hashA+(int)a[i]*(powermax/rr))%M1;
hashA2=(hashA2+(int)a[i]*(powermax/rr))%M2;
rr*=256;
}
rr=1;
for(int i=0;i<length;i++)
{
hashB=(hashB+(int)b[i]*(powermax/rr))%M1;
hashB2=(hashB2+(int)b[i]*(powermax/rr))%M2;
rr*=256;
}
int k=0;
if(hashA==hashB&&hashA2==hashB2)
{
nr++;
v[++k]=0;
}
int lengthB=strlen(b);
for(int i=length;i<lengthB;i++)
{
hashB=((hashB*256+b[i])%M1-(b[i-length]*powermax*256)%M1+M1)%M1;
hashB2=((hashB2*256+b[i])%M2-(b[i-length]*powermax*256)%M2+M2)%M2;
if(hashB==hashA&&hashA2==hashB2)
{
nr++;
v[++k]=i-length+1;
}
}
g<<nr<<"\n";
for(int i=1;i<=k&&k<=1000;i++)
g<<v[i]<<" ";
return 0;
}