Pagini recente » Cod sursa (job #3264622) | Profil EugenStoica | Cod sursa (job #3245753) | Cod sursa (job #323233) | Cod sursa (job #1309190)
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#include <cstring>
string s,t;
#define LE 5000666
#define cout g
int i,M[LE],j;
void Zalg(int nt)
{
int N=t.size();
int st=0,dr=0,i;
for(i=1; i<N; ++i)
{
int start=0;
if (dr>=i) M[i]=M[i-st];
if (i+M[i]>dr) start=i;
else start=i+M[i];
if (i==474+nt)
bool xoxo=true;
if (i+M[i]-1>=dr)
{
for(j=start;j-i<nt&& j<N&&t[j-i]==t[j]; ++j)
bool te=false;
M[i]=(j-1)-i+1;
dr=i+M[i]-1;
st=i;
}
}
}
int main()
{
f>>s>>t;
swap(s,t);
int ns=s.length();
int nt=t.length();
t+=s;
// cout<<t<<'\n';
int N=t.length();
Zalg(nt);
int nr_sol=0;
int res=0;
for(i=nt;i<N;++i)
if (M[i]>=nt) ++res;
cout<<res<<'\n';
for(i=nt; i<N; ++i)
{
if (M[i]<nt) continue;
++nr_sol;
cout<<i-nt<<" ";
if (nr_sol==1000) break;
}
return 0;
}