Pagini recente » Cod sursa (job #3222640) | Cod sursa (job #2758632) | Cod sursa (job #2938803) | Cod sursa (job #1506513) | Cod sursa (job #1262502)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char a[2000007],b[2000007];
int MOD1=299777;
int MOD2=299771;
bool ans[2000007];
int main()
{
cin>>a;
cin>>b;
int lga=strlen(a);
int lgb=strlen(b);
int smallhash1=0;
int smallhash2=0;
int putmax1=1;
int putmax2=1;
for ( int i = 0 ; i <= lga ; ++i )
{
smallhash1=(smallhash1*71+a[i])%MOD1;
smallhash2=(smallhash2*71+a[i])%MOD2;
if ( i )
{
putmax1=(putmax1*71)%MOD1;
putmax2=(putmax2*71)%MOD2;
}
}
if ( lga > lgb )
{
cout<<0<<'\n';
return 0;
}
int bighash1=0;
int bighash2=0;
for ( int i = 0 ; i < lga ; ++i )
{
bighash1=(bighash1*71+b[i])%MOD1;
bighash2=(bighash2*71+b[i])%MOD2;
}
int sol = 0 ;
if ( smallhash1==bighash1 and smallhash2==bighash2);
{
ans[0]=1;
++sol;
}
for ( int i = lga ; i<= lgb ; ++i )
{
bighash1=(((bighash1-b[i-lga]*putmax1)%MOD1+MOD1)*71+b[i])%MOD1;
bighash2=(((bighash2-b[i-lgb]*putmax2)%MOD2+MOD2)*71+b[i])%MOD2;
if ( smallhash1==bighash1 and smallhash2==bighash2 )
{
ans[i-lga+1]=1;
sol++;
}
}
cout<<sol<<'\n';
sol=1;
for ( int i = 0 ; i < lgb and sol<=1000 ; ++i )
if (ans[i]!=0)
{
cout<<i<<" ";
++sol;
}
cout<<'\n';
return 0;
}