Pagini recente » Cod sursa (job #807719) | Cod sursa (job #735430) | Cod sursa (job #2141794) | Cod sursa (job #1684053) | Cod sursa (job #2739412)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s,s1,s2;
int poz[2000005],z[4000005],k,val,lim,i,q,st,dr,cop;
int main()
{
f>>s;
f>>s1;
s2=s+'#'+s1;
st=0;
dr=0;
for (i=1;i<s2.size();i++)
{
if (i<=dr)
{
z[i]=min(dr-i+1,z[i-st]);
}
while (i+z[i]<s2.size()&&s2[i+z[i]]==s2[z[i]])
{
z[i]++;
}
if (i+z[i]-1>dr)
{
st=i;
dr=i+z[i]-1;
}
if (z[i]==s.size())
{
poz[++q]=i-s.size()-1;
}
}
g<<q<<'\n';
lim=min(q,1000);
for (i=1;i<=lim;i++)
{
g<<poz[i]<<" ";
}
return 0;
}