Pagini recente » Cod sursa (job #689221) | Cod sursa (job #2265886) | Cod sursa (job #2890701) | Cod sursa (job #3291861) | Cod sursa (job #195309)
Cod sursa(job #195309)
#include <cstdio>
#include <cstring>
#define MAX_LENGTH 2000001
char N[MAX_LENGTH], M[MAX_LENGTH];
int n,m;
int PI[MAX_LENGTH];
void functiePrefix()
{
int k=-1;
PI[0]=0;
for (int i=1;i<n;i++)
{
while(k>0 && (N[k+1] != N[i]))
k = PI[k];
if (N[k+1] == N[i])
k++;
PI[i] = k;
}
}
void calculeazaSiruri()
{
int Occurences[MAX_LENGTH];
int iNrOccurences=0;
int q = -1;
for (int i=0;i<m;i++)
{
while(q > 0 && (N[q+1] != M[i]))
q = PI[q];
if (N[q+1] == M[i])
q++;
if (q == n-1)
{
Occurences[iNrOccurences++]=i-n+1;
q = PI[q];
}
}
printf("%d\n",iNrOccurences);
for (int i=0;i<iNrOccurences;i++)
printf("%d ",Occurences[i]);
printf("\n");
}
int main()
{
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
scanf("%s\n",&N);
scanf("%s\n",&M);
n=strlen(N);
m=strlen(M);
functiePrefix();
calculeazaSiruri();
return 0;
}