Pagini recente » Cod sursa (job #539689) | Cod sursa (job #1770993) | Cod sursa (job #897911) | Cod sursa (job #2964787) | Cod sursa (job #676711)
Cod sursa(job #676711)
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define Nmax 2000005
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
using namespace std;
int n, m, q;
int L[Nmax], pz[1005];
char T[Nmax], P[Nmax];
void read();
void prefix();
void solve();
void write();
int main()
{
assert (freopen (InFile, "r", stdin));
assert (freopen (OutFile, "w", stdout));
read();
prefix();
solve();
write();
return 0;
}
void read()
{
scanf ("%s\n", P+1);
m=strlen (P+1);
scanf ("%s\n", T+1);
n=strlen (T+1);
}
void prefix()
{
int i, k;
L[1]=0;
for (i=2; i<=m; i++)
{
k=L[i-1];
while (k>0 && P[k+1]!=P[i])
k=L[k];
if (P[k+1]==P[i])
k++;
L[i]=k;
}
}
void solve()
{
int i, k;
k=L[1];
for (i=1; i<=n; i++)
{
while (k>0 && P[k+1]!=T[i])
k=L[k];
if (P[k+1]==T[i])
k++;
if (k==m)
{
if (q<1000)
pz[q]=i-k;
q++;
k=L[k];
}
}
}
void write()
{
int i;
printf ("%d\n", q);
for (i=0; i<min (q, 1000); i++)
printf ("%d ", pz[i]);
printf ("\n");
}