Pagini recente » Cod sursa (job #3216916) | Cod sursa (job #1118821) | Cod sursa (job #320444) | Cod sursa (job #1033349) | Cod sursa (job #302717)
Cod sursa(job #302717)
#include<fstream.h>
#include<string.h>
#define nx 2000005
char A[nx],B[nx];
int pi[nx],poz[1005],n,m;
void makep()
{
int i,k=0;
for (i=2;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()
{
ifstream be ("strmatch.in");
ofstream ki ("strmatch.out");
be>>A>>B;
int x=0,i,k;
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]=' ';
makep();
k=0;
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)
poz[x]=i-n;
}
}
ki<<x<<'\n';
for (i=1;i<=x && i<=1000;++i)
ki<<poz[i]<<" ";
ki<<'\n';
ki.close();
return 0;
}