Pagini recente » Cod sursa (job #931214) | ONIS 2014, Runda 2 | Cod sursa (job #326729) | Cod sursa (job #1609899) | Cod sursa (job #1126418)
#include <cstdio>
#include <cstring>
#define nmax 2000010
using namespace std;
char N[nmax],M[nmax];
int n,m,nr,sol[nmax],key[nmax];
void prefix()
{
int x=0,i;
key[1]=0;
for(i=2;i<=n;i++)
{
while(x>0 && N[x+1]!=N[i])
x=key[x];
if(N[x+1]==N[i])
x++;
key[i]=x;
}
}
void match()
{
int i,x=0;
for(i=1;i<=m;i++)
{
while(x>0 && N[x+1]!=M[i])
x=key[x];
if(N[x+1]==M[i])
x++;
if(x==n)
sol[++nr]=i-n;
}
}
void afisare()
{
int i;
printf("%d\n",nr);
for(i=1;i<=nr;i++)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(N+1);
n=strlen(N+1);
gets(M+1);
m=strlen(M+1);
prefix();
match();
afisare();
return 0;
}