Pagini recente » Cod sursa (job #1491715) | Cod sursa (job #2865054) | Cod sursa (job #216623) | Cod sursa (job #1616782) | Cod sursa (job #292477)
Cod sursa(job #292477)
#include<fstream.h>
#include<string.h>
#define nx 2000005
char A[nx],B[nx];
int n,m;
int pi[nx],pos[nx];
void make_prefix()
{
int i,k=0;
for (i=2,pi[1]=0;i<=n;++i)
{
while (k && A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i])
++k;
pi[i]=k;
}
}
int main()
{
int x=0,k=0,i;
ifstream be ("strmatch.in");
ofstream ki ("strmatch.out");
be>>A>>B;
be.close();
n=strlen(A),m=strlen(B);
for (i=n;i;--i)
A[i]=A[i-1];
A[0]=' ';
for (i=m;i;--i)
B[i]=B[i-1];
B[0]=' ';
make_prefix();
for (i=1;i<=m;++i)
{
while (k && A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==n)
{
k=pi[n];
++x;
if (x<=1000) pos[x]=i-n;
}
}
ki<<x<<'\n';
for (i=1;i<=x && i<=1000;++i)
ki<<pos[i]<<' ';
ki<<'\n';
ki.close();
return 0;
}