Pagini recente » Cod sursa (job #1662003) | Cod sursa (job #2364532) | Borderou de evaluare (job #1569369) | Cod sursa (job #2955192) | Cod sursa (job #3300535)
#include <fstream>
#define int long long
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int q1=1e9+7;
const int q2=666013;
const int B=263;
const int NMAX=2*1e6+5;
char p[NMAX], t[NMAX];
int ans[1005];
signed main()
{
cin>>p;
cin>>t;
int i, hshp1=0, hshp2=0, pw1=1, pw2=1, hsht1=0, hsht2=0;
for(i=0; p[i]; i++)
{
hshp1=(hshp1*B+p[i])%q1;
hshp2=(hshp2*B+p[i])%q2;
if(p[i+1])
{
pw1=(pw1*B)%q1;
pw2=(pw2*B)%q2;
}
hsht1=(hsht1*B+t[i])%q1;
hsht2=(hsht2*B+t[i])%q2;
}
int m=i, cnt=0;
for(i=0; t[i+m-1]; i++)
{
if(hsht1==hshp1 && hsht2==hshp2)
{
cnt++;
if(cnt<=1000) ans[cnt]=i;
}
hsht1=((hsht1+q1-(t[i]*pw1)%q1)*B+t[i+m])%q1;
hsht2=((hsht2+q2-(t[i]*pw2)%q2)*B+t[i+m])%q2;
}
cout<<cnt<<'\n';
for(i=1; i<=min(cnt, 1LL*1000); i++) cout<<ans[i]<<' ';
return 0;
}