Pagini recente » Cod sursa (job #353691) | Cod sursa (job #197744) | Cod sursa (job #1285256) | Cod sursa (job #1423876) | Cod sursa (job #145380)
Cod sursa(job #145380)
#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 = 0;
int 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);
scanf ("%s", P + 1);
scanf ("%s", T + 1);
m = strlen (P + 1); n = strlen (T + 1);
prefix ();
int i;
for ( int k = 0, i = 1; i <= n; ++i )
{
while ( k && P[k+1] != T[i] )
k = U[k];
if ( P[k+1] == T[i] )
++k;
if ( k == m )
{
++cnt;
if ( cnt <= 1000 )
S[cnt] = i - m;
}
}
printf ("%d\n", cnt);
for (i = 1; i <= cnt && i <= 1000; ++i) printf ("%d ", S[i]);
return 0;
}