Pagini recente » Cod sursa (job #1645887) | Cod sursa (job #1237790) | Cod sursa (job #2222181) | Cod sursa (job #1050432) | Cod sursa (job #229627)
Cod sursa(job #229627)
#include<stdio.h>
#include<string.h>
char a[2000005];
char b[2000005];
int P[2000005];
int sir[2000005];
int nr;
int la;
int k;
int lb;
void Kmprefix()
{
int k = 0;
for(int i = 2; i <= la; i++)
{
while (k > 0 && a[k] != a[i-1])
k = P[k];
if (a[k] == a[i-1]) k++;
P[i] = k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",&a,&b);
la = strlen(a);
lb = strlen(b);
Kmprefix();
k = 0;
for(int i = 1; i <= lb; i++)
{
while (k > 0 && a[k] != b[i-1])
k = P[k];
if (a[k] == b[i-1]) k++;
if (k == la)
{
nr++;
if (nr <= 1000)
sir[++sir[0]] = i - la;
}
}
printf("%d \n",nr);
for(int i = 1;i <= sir[0]; i++)
printf("%d ",sir[i]);
return 0;
}