Pagini recente » Cod sursa (job #2405040) | Cod sursa (job #346038) | Cod sursa (job #69032) | Cod sursa (job #1714732) | Cod sursa (job #169900)
Cod sursa(job #169900)
#include <stdio.h>
#include <string.h>
#define MAXL 2000100
char A[MAXL],B[MAXL];
int pi[MAXL];
int R[1005],r;
int nA,nB;
void calcpi()
{
int k=0,i;
pi[1]=0;
for (i=2; i<=nA; ++i)
{
while (k>0 && A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i])
++k;
pi[i]=k;
}
}
void rezolv()
{
int k=0,i;
for (i=1; i<=nB; ++i)
{
while (k>0 && A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==nA)
{
if (r<1000)
R[r++]=i-nA;
else
r++;
}
}
}
void afisare()
{
printf("%d\n",r);
if (r)
{
printf("%d",R[0]);
for (int i=1; i<r && i<1000; i++)
printf(" %d",R[i]);
printf("\n");
}
}
void citire()
{
fgets(A+1,MAXL,stdin);
fgets(B+1,MAXL,stdin);
nA=strlen(A+1); nA++;
while ( !( (A[nA]>='A' && A[nA]<='Z') || (A[nA]>='a' && A[nA]<='z') || (A[nA]>='0' && A[nA]<='9')) )
nA--;
nB=strlen(B+1); nB++;
while ( !( (B[nB]>='A' && B[nB]<='Z') || (B[nB]>='a' && B[nB]<='z') || (B[nB]>='0' && B[nB]<='9')) )
nB--;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
calcpi();
rezolv();
afisare();
fclose(stdin);
fclose(stdout);
return 0;
}