Pagini recente » Cod sursa (job #2173192) | Cod sursa (job #1169523) | Cod sursa (job #703426) | Cod sursa (job #1416224) | Cod sursa (job #432397)
Cod sursa(job #432397)
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define DIM 2000005
char s1[DIM],s2[DIM];
vector <int> sol;
int pi[DIM];
int n,m,nrt;
void prefix ()
{
int i,k;
pi[1]=0;
for (k=0, i=2; i<=n; ++i)
{
for ( ; k>0 && s1[k+1]!=s1[i]; k=pi[k]);
if (s1[k+1]==s1[i])
++k;
pi[i]=k;
}
}
void solve ()
{
int i,k;
n=strlen (s1+1)-1;
m=strlen (s2+1)-1;
prefix ();
for (k=0, i=1; i<=m; ++i)
{
for ( ; k>0 && s1[k+1]!=s2[i]; k=pi[k]);
if (s1[k+1]==s2[i])
++k;
if (k==n)
{
if (++nrt<=1000)
sol.pb (i-k);
}
}
}
void print ()
{
vector <int> :: iterator it;
printf ("%d\n",nrt);
for (it=sol.begin (); it!=sol.end (); ++it)
printf ("%d ",*it);
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
fgets (s1+1,DIM,stdin);
fgets (s2+1,DIM,stdin);
solve ();
print ();
return 0;
}