Pagini recente » Cod sursa (job #1608504) | Cod sursa (job #587660) | Cod sursa (job #48158) | Cod sursa (job #2799280) | Cod sursa (job #1867500)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define MOD1 666013
#define MOD2 10003
int h1,h2,m,n,i,sol[10004],s,nr,v1,v2,p1,p2;
char a[2000012],b[2000012];
int main()
{
f.getline(a,2000012);
f.getline(b,2000012);
m=strlen(a);
n=strlen(b);
p1=1;
p2=1;
for(i=0; i<m; ++i)
{
h1=(h1*101%MOD1+(int)a[i])%MOD1;
h2=(h2*109%MOD2+(int)a[i])%MOD2;
v1=(v1*101%MOD1+(int)b[i])%MOD1;
v2=(v2*109%MOD2+(int)b[i])%MOD2;
if (i>0)
{
p1*=101;
p1%=MOD1;
p2*=109;
p2%=MOD2;
}
}
if (v1==h1 && v2==h2)
{
nr++;
sol[++s]=i-m;
}
for (i=m; i<n; i++)
{
// v1 = ((((v1 - (int)b[i-m]*p1)*101)% MOD1 + MOD1)*101 + (int)b[i])%MOD1;
// v2 = ((((v2 - (int)b[i-m]*p2)*109)% MOD2 + MOD2)*109 + (int)b[i])%MOD2;
v1 = (( v1-( int (b[i-m])*p1 ) % MOD1 + MOD1) * 101 + int(b[i])) % MOD1;
v2 = (( v2- (int (b[i-m])*p2 ) % MOD2 + MOD2) * 109 + int(b[i])) % MOD2;
if (v1==h1 && v2==h2)
{
nr++;
if(nr<=1000)
sol[++s]=i-m+1;
}
}
g<<nr<<'\n';
for(i=1; i<=s; ++i)
g<<sol[i]<<" ";
return 0;
}