Pagini recente » Cod sursa (job #676126) | Cod sursa (job #2779758) | Cod sursa (job #1725191) | Cod sursa (job #2510929) | Cod sursa (job #1253941)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
string a,b;
int i,j,la,l,r,Z[2000005*2],ans;
vector<int> rasp;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void expand(){while(a[r+1] == a[r-l+1] && r + 1 < a.size())++r;}
int main()
{
cin>>a>>b;
la=a.size();
a+=b;
Z[0]=a.size();
for(i=1;i<a.size();++i)
{
Z[i]=0;
if (l <= i && i <= r)
{
if (Z[i-l]>=r-i+1)
{
l=i;
expand();
Z[i]=r-l+1;
}
else Z[i]=Z[i-l];
}
else if (a[i] == a[0])
{
l=r=i;
expand();
Z[i]=r-l+1;
}
//cout<<"I = "<<i<<" , "<<"L = "<<l<<" , "<<"R = "<<r<<" , "<<"Z[i] = "<<Z[i]<<'\n';
}
for (i=la;i<=a.size();++i)
if (Z[i]>=la)
{
++ans;
if (ans<=1000)
{
rasp.push_back(i);
}
}
cout<<ans<<'\n';
for(i=0;i<rasp.size();++i)
cout<<rasp[i]-la<<" ";
return 0;
}