Pagini recente » Cod sursa (job #171862) | Cod sursa (job #1356671) | Cod sursa (job #1774818) | Cod sursa (job #1528031) | Cod sursa (job #2376483)
#include <stdio.h>
#define MAXN 2000005
#define minim(a, b) ((a < b) ? a : b)
using namespace std;
int M, N;
char a[MAXN], b[MAXN];
int pi[MAXN], pos[1024];
void makePrefix(void)
{
int i, q = 0;
for(i = 2, pi[1] = 0; i <= M; ++i)
{
while(q && a[q+1] != a[i])
q = pi[q];
if(a[q+1] == a[i])
++q;
pi[i] = q;
}
}
int main(void)
{
int i, q = 0, n = 0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
for(; (a[M] >= 'A' && a[M] <= 'Z') ||
(a[M] >= 'a' && a[M] <= 'z') ||
(a[M] >= '0' && a[M] <= '9'); M++)
for(; (b[N] >= 'A' && b[N] <= 'Z') ||
(b[N] >= 'a' && b[N] <= 'z') ||
(b[N] >= '0' && b[N] <= '9'); N++)
for(i = M; i; --i) a[i] = a[i-1]; a[0] = ' ';
for(i = N; i; --i) b[i] = b[i-1]; b[0] = ' ';
makePrefix();
for(i = q; i <= N; ++i)
{
while(q && a[q+1] != b[i])
q = pi[q];
if(a[q+1] == b[i])
++q;
if(q == M)
{
q = pi[M];
++n;
if(n <= 1000)
pos[n] = i-M;
}
}
printf("%d\n", n);
for(i = 1; i <= minim(n, 1000); ++i)
printf("%d", pos[i]);
printf("\n");
return 0;
}