Pagini recente » Cod sursa (job #2482250) | Cod sursa (job #1646371) | Cod sursa (job #262429) | Cod sursa (job #2307853) | Cod sursa (job #3231666)
#include <bits/stdc++.h>
#define mod1 666013
#define mod2 10003
#define bz 127
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
bool ok[2000001];
char a[2000001],b[2000001];
int na,nb,h1,h2,v1,v2,bz1,bz2,nr;
int main()
{
f >> a >> b;
na=strlen(a);
nb=strlen(b);
if ( na>nb )
{
g << 0;
return 0;
}
bz1=1;
bz2=1;
for (int i=0; i<na; i++ )
{
h1=(h1*bz+a[i])%mod1;
h2=(h2*bz+a[i])%mod2;
if ( i>0 )
{
bz1=(bz1*bz)%mod1;
bz2=(bz2*bz)%mod2;
}
v1=(v1*bz+b[i])%mod1;
v2=(v2*bz+b[i])%mod2;
}
if ( v1==h1 && v2==h2 )
{
ok[0]=true;
nr++;
}
for (int i=na; i<nb; i++ )
{
v1=((v1-(b[i-na]*bz1)%mod1+mod1)*bz+b[i])%mod1;
v2=((v2-(b[i-na]*bz2)%mod2+mod2)*bz+b[i])%mod2;
if ( v1==h1 && v2==h2 )
{
ok[i-na+1]=true;
nr++;
}
}
g << nr;
g << '\n';
nr=0;
for (int i=0; i<nb && nr<1000; i++ )
if ( ok[i] )
{
nr++;
g << i << " ";
}
return 0;
}