Pagini recente » Cod sursa (job #2292245) | Cod sursa (job #233461) | Cod sursa (job #1577722) | Cod sursa (job #1160297) | Cod sursa (job #145368)
Cod sursa(job #145368)
#include <cstdio>
#include <cstring>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX_N 2000005
int U[MAX_N];
char T[MAX_N], P[MAX_N];
int S[1010];
int n, m;
int cnt;
void prefix ()
{
int k = -1;
int i;
U[0] = 0;
for (i = 1; 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);
gets (T);
//m = strlen (P); n = strlen (T);
for (; (P[m] >= 'A' && P[m] <= 'Z') || (P[m] >= 'a' && P[m] <= 'z')
|| (P[m] >= '0' && P[m] <= '9'); ++m);
for (; (T[n] >= 'A' && T[n] <= 'Z') || (T[n] >= 'a' && T[n] <= 'z')
|| (T[n] >= '0' && T[n] <= '9'); ++n);
prefix ();
int i;
int x = -1;
for (i = 0; i < n; ++i)
{
while (x > 0 && P[x + 1] != T[i]) x = U[x];
if (P[x + 1] == T[i]) ++x;
if (x == m - 1)
{
x = U[x];
if (cnt < 1005)
S[++cnt] = i - m + 1;
else ++cnt;
}
}
printf ("%d\n", cnt);
for (i = 1; i <= cnt && i <= 1000; ++i) printf ("%d ", S[i]);
return 0;
}