Pagini recente » Cod sursa (job #436819) | Cod sursa (job #2468364) | Cod sursa (job #2822481) | Cod sursa (job #768327) | Cod sursa (job #344207)
Cod sursa(job #344207)
#include<stdio.h>
#include<string.h>
char A[2000005],B[2000005];
int lA;
int contor;
int sirmatch[1005];
int lB;
int P[2000005];
int now;
int min(int r1, int r2)
{
if (r1 < r2) return r1;
return r2;
}
void Prefix()
{
int now = 0;
for(int i = 1; i < lA; i++)
{
now = P[i-1];
while (A[now] != A[i] && now > 0)
{
now = P[now];
}
if (A[now] == A[i]) now++;
P[i] = now;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&A,&B);
lA = strlen(A);
lB = strlen(B);
Prefix();
now = 0;
for(int i = 0; i <= lB; i++)
{
while (A[now] != B[i] && now > 0)
{
now = P[now];
}
if (A[now] == B[i])
now++;
if (now == lA)
{
contor++;
if (contor <= 1000)
{
sirmatch[contor] = i - lA + 1;
}
now = P[lA-1];
}
}
printf("%d\n",contor);
for(int i = 1; i <= min(contor,1000);i++)
printf("%d ",sirmatch[i]);
return 0;
}