Pagini recente » Cod sursa (job #1979795) | Cod sursa (job #696224) | Cod sursa (job #2880574) | Cod sursa (job #2915005) | Cod sursa (job #377451)
Cod sursa(job #377451)
#include<fstream.h>
int i,prefix[2001000],poz[1100],k,nr,n,m;
char a[2001000],b[2001000];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(a,2001000);
f.getline(b,2001000);
n=strlen(a);
m=strlen(b);
for(i=n;i;i--)
a[i]=a[i-1];
for(i=m;i;i--)
b[i]=b[i-1];
prefix[1]=0;
k=0;
for(i=2;i<=n;i++)
{
while(k>0&&a[k+1]!=a[i])
k=prefix[k];
if(a[k+1]==a[i])
k++;
prefix[i]=k;
}
i=1;
k=0;
for(i=1;i<=m;i++)
{
while(k&&a[k+1]!=b[i])
k=prefix[k];
if(a[k+1]==b[i])
k++;
if(k==n)
{
k=prefix[n];
nr++;
if(n<=1000)
poz[nr]=i-n;
}
}
if(nr>1000)
k=1000;
else
k=nr;
g<<nr<<'\n';
for(i=1;i<=k;i++)
g<<poz[i]<<' ';
return 0;
}