Pagini recente » Diferente pentru utilizator/deea intre reviziile 1 si 2 | Cod sursa (job #2159338) | Cod sursa (job #1317348) | Monitorul de evaluare | Cod sursa (job #1629593)
#include <bits/stdc++.h>
using namespace std;
string z = "strmatch.";
ifstream f(z+"in");
ofstream g(z+"out");
int i,j,la,l,r,Z[2000005*2],ans;
string a,b;
vector<int> rasp;
void expand(){while(a[r+1] == a[r-l+1] && r + 1 < a.size())++r;}
int main()
{
f>>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;
}
}
for (i=la;i<=a.size();++i)
if (Z[i]>=la)
{
++ans;
if (ans<=1000)
{
rasp.push_back(i);
}
}
g<<ans<<'\n';
for(i=0;i<rasp.size();++i)
g<<rasp[i]-la<<" ";
return 0;
}