Pagini recente » Cod sursa (job #2975718) | Cod sursa (job #2720742) | Cod sursa (job #802943) | Cod sursa (job #2720219) | Cod sursa (job #488872)
Cod sursa(job #488872)
#include <stdio.h>
#include <string.h>
const long Nmax = 2000005;
const int meg = 1001;
char A[Nmax], B[Nmax];
long next[Nmax], pos[meg];
long n,m;
long N = 0;
void olvas();
void prefix();
void egyeb();
void kiir();
int main()
{
olvas();
prefix();
egyeb();
kiir();
return 0;
}
void olvas()
{
freopen("strmatch.in", "r", stdin);
fgets(B, sizeof(B), stdin);
fgets(A, sizeof(A), stdin);
n = strlen(A);
m = strlen(B);
if (B[m-1] == '\n')
m--;
if (A[n-1] == '\n')
n--;
for (int i=n;i>0;i--)
A[i] = A[i-1];
A[0] = ' ';
for (int i=m;i>0;i--)
B[i] = B[i-1];
B[0] = ' ';
}
void prefix()
{
long k = 0;
next[1] = 0;
for (int q = 2; q<=m; q++)
{
while ((k) && (B[k+1] != B[q]))
k = next[k];
if (B[k+1] == B[q])
k++;
next[q] = k;
}
}
void egyeb()
{
long i = 0;
long k = 0;
while (++i<=n)
{
while ((k) && (B[k+1] != A[i]))
k = next[k];
if (B[k+1] == A[i])
k++;
if (k == m)
{
k = next[m];
++N;
if (N < meg) pos[N] = i-m;
}
}
}
void kiir()
{
freopen("strmatch.out", "w", stdout);
printf("%ld\n",N);
long nn = N;
if (N>=meg) nn = meg-1;
for (int i = 1; i<= nn; i++)
printf("%ld ", pos[i]);
}