Pagini recente » Cod sursa (job #2910308) | Cod sursa (job #2601347) | Cod sursa (job #779240) | Cod sursa (job #680195) | Cod sursa (job #3288361)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string n,m;
int len,lps[2000005],i,v[1005],k,sz,j;
int main()
{
in>>n>>m;
for(i=1; n[i]; ++i)
{
if(n[i]==n[len])
++len,lps[i]=len;
else if(!len)
lps[i]=0;
else
{
while(len)
{
len=lps[len-1];
if(n[i]==n[len])
{
++len;
lps[i]=len;
break;
}
}
}
}
sz=n.size();
for(i=0,j=0; m[i]; ++i)
{
if(m[i]==n[j])
{
++j;
if(j==sz)
{
++k;
if(k<=1000)
v[k]=i+1-sz;
j=lps[j-1];
}
}
else if(j)
j=lps[j-1],--i;
}
out<<k<<'\n';
for(i=1; i<=min(1000,k); ++i)
out<<v[i]<<' ';
}