Pagini recente » Cod sursa (job #275159) | Cod sursa (job #2053642) | Cod sursa (job #2108003) | Cod sursa (job #99521) | Cod sursa (job #1543115)
#include <fstream>
#include <cstring>
#define M1 100007
#define M2 100021
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001],b[2000001];
long v[1001],nr;
int p=256;
int main()
{
int hashA=0,hashB=0,hashA2=0,hashB2=0;
f.getline(a,2000001);
f.getline(b,2000001);
int length=strlen(a);
int lengthB=strlen(b);
int p1=1,p2=1;
for(int i=0;i<length;i++)
{
hashA=(hashA*p+a[i])%M1;
hashA2=(hashA2*p+a[i])%M2;
hashB=(hashB*p+b[i])%M1;
hashB2=(hashB2*p+b[i])%M2;
if(i!=0)
{
p1=(p1*p)%M1;
p2=(p2*p)%M2;
}
}
if(hashA==hashB&&hashA2==hashB2)
{
nr++;
v[nr]=0;
}
for(int i=length;i<lengthB;i++)
{
hashB=((hashB-(b[i-length]*p1)%M1+M1)*p+b[i])%M1;
hashB2=((hashB2-(b[i-length]*p2)%M2+M2)*p+b[i])%M2;
if(hashB==hashA&&hashA2==hashB2)
{
nr++;
if(nr<=1000)
v[nr]=i-length+1;
}
}
g<<nr<<"\n";
for(int i=1;i<=nr&&i<=1000;i++)
g<<v[i]<<" ";
return 0;
}