Cod sursa(job #723958)
#include <string>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000005
int m, n;
char a[NMax], b[NMax];
int pi[NMax], pos[1024];
vector <int> sol;
void read()
{
char c;
while((c=fin.get()) && (c!='\n'))
a[++n]=c;
while((c=fin.get()) && (c!='\n') && (c!=EOF))
b[++m]=c;
}
void make_prefix()
{
int q=0,i;
for(i=2;i<=n;++i)
{
while(q!=0 && a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
void solve()
{
int i, q=0,nr=0;
for(i=2;i<=m;++i)
{
while(q!=0 && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==n)
{
q=pi[n];
++nr;
if(nr<=1000)
sol.push_back(i-n);
}
}
fout<<sol.size()<<'\n';
for(unsigned k=0;k<sol.size();++k)
fout<<sol[k] <<" ";
}
int main()
{
read();
make_prefix();
solve();
return 0;
}