Pagini recente » Profil marta_dianna | Monitorul de evaluare | Profil tomescu_dorinel | Profil Ionut228 | Cod sursa (job #907366)
Cod sursa(job #907366)
#include <cstdio>
#include <cstring>
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
char A[2000001],B[2000001];
int M,N,i,j,k;
int v[1001],lps[2000001];
void creare_lps(int M, int lps[], char A[])
{
int len=0, i=1;
lps[0]=0;
while(i<M)
{
if(A[len]==A[i])
{
len++;
lps[i]=len;
i++;
}
else
{
if(len!=0)
len=lps[len-1];
else
{
lps[i]=0;
i++;
}
}
}
}
int main()
{
fscanf(f,"%s %s",A,B);
M=strlen(A);
N=strlen(B);
creare_lps(M,lps,A);
i=0;
j=0;
while(i<N)
{
if(B[i]==A[j])
{
i++;
j++;
}
if(j==M)
{
if(k<=1000)
{
k++;
v[k]=i-j;
}
else
break;
j=lps[j-1];
}
else
if(B[i]!=A[j])
{
if(j!=0)
j=lps[j-1];
else
i++;
}
}
fprintf(g,"%d\n",k);
for(i=1;i<=k;i++)
fprintf(g,"%d ",v[i]);
fclose(f);
fclose(g);
return 0;
}