Pagini recente » Cod sursa (job #246146) | Cod sursa (job #3283636) | Cod sursa (job #854810) | Cod sursa (job #2157251) | Cod sursa (job #525591)
Cod sursa(job #525591)
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define DIM 2000005
char a[DIM],b[DIM];
vector <int> v;
int pi[DIM];
int n,m,nrt;
void read ()
{
fgets (a+1,DIM,stdin);
n=strlen (a+1)-(a[strlen (a+1)]=='\n');
fgets (b+1,DIM,stdin);
m=strlen (b+1)-(b[strlen (b+1)]=='\n');
}
void solve ()
{
int i,k;
for (i=2; i<=n; ++i)
{
for ( ; k && a[k+1]!=a[i]; k=pi[k]);
if (a[k+1]==a[i])
++k;
pi[i]=k;
}
for (k=0, i=1; i<=m; ++i)
{
for ( ; k && a[k+1]!=b[i]; k=pi[k]);
if (a[k+1]==b[i])
++k;
if (k==n)
{
if (++nrt<=1000)
v.pb (i-k);
}
}
}
void print ()
{
vector <int> :: iterator it;
printf ("%d\n",nrt);
for (it=v.begin ();it!=v.end (); ++it)
printf ("%d ",*it);
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
read ();
solve ();
print ();
return 0;
}