Pagini recente » Cod sursa (job #29467) | Cod sursa (job #526278) | Cod sursa (job #1764126) | Cod sursa (job #758504) | Cod sursa (job #356132)
Cod sursa(job #356132)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000005
char P[MAX_N], C[MAX_N];
int U[MAX_N], S[1 << 10];
int N, M;
void prefix ()
{
int k = 0, i;
U[0] = 0;
for (i = 2; i <= M; ++i)
{
while (k > 0 && P[k + 1] != P[i]) k = U[k];
if (P[k + 1] == P[i]) ++k;
U[i] = k;
}
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
gets (P + 1);
gets (C + 1);
N = strlen (C + 1), M = strlen (P + 1);
prefix ();
int i, k = 0, cnt = 0, STOP = 0;
for (i = 1; i <= N; ++i)
{
while (k > 0 && C[i] != P[k + 1]) k = U[k];
if (C[i] == P[k + 1]) ++k;
if (k == M && !STOP)
S[++cnt] = i - M;
else
if (k == M) ++cnt;
if (cnt == 1000) STOP = 1;
}
printf ("%d\n", cnt);
for (i = 1; i <= cnt && i <= 1000; ++i) printf ("%d ", S[i]);
return 0;
}