Pagini recente » Istoria paginii jc2016/runda-2 | Cod sursa (job #3176827) | Istoria paginii monthly-2012/runda-3/clasament | Rating Morariu (MorariuT) | Cod sursa (job #3300532)
#include <fstream>
#define int long long
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int q=1e9+7;
const int B=263;
const int NMAX=2*1e6+5;
char p[NMAX], t[NMAX];
int ans[1005];
bool check(int poz)
{
int i;
for(i=0; p[i]; i++)
{
if(p[i]!=t[i+poz]) return false;
}
return true;
}
signed main()
{
cin>>p;
cin>>t;
int i, hshp=0, pw=1, hsht=0;
for(i=0; p[i]; i++)
{
hshp=(hshp*B+p[i])%q;
if(p[i+1]) pw=(pw*B)%q;
hsht=(hsht*B+t[i])%q;
}
int m=i, cnt=0;
for(i=0; t[i+m-1]; i++)
{
if(hsht==hshp)
{
if(check(i))
{
cnt++;
if(cnt<=1000) ans[cnt]=i;
}
}
hsht=((hsht+q-(t[i]*pw)%q)*B+t[i+m])%q;
}
cout<<cnt<<'\n';
for(i=1; i<=min(cnt, 1LL*1000); i++) cout<<ans[i]<<' ';
return 0;
}