Pagini recente » Cod sursa (job #750515) | Cod sursa (job #2902848) | Cod sursa (job #2488603) | Cod sursa (job #1900824) | Cod sursa (job #2231543)
#include <fstream>
#include <cstring>
using namespace std;
int n,m,i,j,nr,v[2000002],afis[1002];
char c[1000], p[2000002];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(c,2000002);
f.get();
f.get(p,2000002);
n=strlen(c);
m=strlen(p);
///construim prefix : (v[x]=cel mai lung prefix pana la poz x care e si sufix)
for(i=1; i<n; i++)
{
while(c[j]!=c[i] && j>0)
j=v[j-1];
if(c[j]==c[i])
{
v[i]=j+1;
j++;
}
}
///
j=0;
for(i=0; i<m; i++)
{
while(p[i]!=c[j] && j>0)
j=v[j-1];
if(p[i]==c[j])
{
if(j==n-1)
{
if(nr<=999)
afis[++nr]=i-n+1;
else
nr++;
}
j++;
}
}
g<<nr<<'\n';
nr=min(nr,1000);
for(i=1;i<=nr;i++)
g<<afis[i]<<' ';
return 0;
}