Pagini recente » Cod sursa (job #635603) | Cod sursa (job #3188999) | Cod sursa (job #212407) | Cod sursa (job #525429) | Cod sursa (job #3231651)
#include <bits/stdc++.h>
#define mod1 100007
#define mod2 100021
#define bz 127
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
bool ok[100005];
char a[100005],b[100005];
int na,nb,h1,h2,v1,v2,bz1,bz2,nr;
int main()
{
f >> a >> b;
na=strlen(a);
nb=strlen(b);
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';
for (int i=0; i<nb; i++ )
if ( ok[i] )
g << i << " ";
return 0;
}