Pagini recente » Cod sursa (job #1522388) | Cod sursa (job #1625509) | Cod sursa (job #2410932) | Cod sursa (job #814348) | Cod sursa (job #228784)
Cod sursa(job #228784)
#include<stdio.h>
#include<string.h>
char a[2000001],b[2000001];
int P[2000001];
int l;
int nr;
int k;
int poz[1005];
void Prefix_Kmp()
{
P[1] = 0;
int k = 0;
l = strlen(a);
for(int i = 2; i <= l; 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);
Prefix_Kmp();
k = 0;
int lb = strlen(b);
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 == l)
{
nr++;
if (nr<1000)
poz[++poz[0]] = i-l;
}
}
printf("%d \n", nr);
for(int i = 1; i <= poz[0]; i++)
printf("%d ",poz[i]);
return 0;
}