Pagini recente » Cod sursa (job #2532996) | Cod sursa (job #130368) | Cod sursa (job #2730520) | Cod sursa (job #1118765) | Cod sursa (job #676708)
Cod sursa(job #676708)
#include <cstdio>
#include <cassert>
#include <cstring>
#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 && q<1000; i++)
{
while (k>0 && P[k+1]!=T[i])
k=L[k];
if (P[k+1]==T[i])
k++;
if (k==m)
{
pz[q++]=i-k;
k=L[k];
}
}
}
void write()
{
int i;
printf ("%d\n", q);
for (i=0; i<q; i++)
printf ("%d ", pz[i]);
printf ("\n");
}