Pagini recente » Cod sursa (job #1865542) | Cod sursa (job #457623) | Cod sursa (job #2574399) | Cod sursa (job #1928116) | Cod sursa (job #2375458)
#include <stdio.h>
#include <string.h>
#define MAXN 2000010
#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;
}