Cod sursa(job #1377178)

Utilizator vladvaldezVlad Dimulescu vladvaldez Data 5 martie 2015 20:37:53
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>

#define NN 2000008
using namespace std;

char s[NN],ss[NN],c;
int n,m,urm[NN],b[1005],o,ct,i,k;


void citire(){

c='0';
n=-1;
while(c!='\n'){
scanf("%c",&c);
if (c!='\n')s[++n]=c;
}
c='0';
m=-1;
while(c!='\n'){
scanf("%c",&c);
if (c!='\n')ss[++m]=c;
}


}

int main()
{
freopen("strmatch.in", "r",stdin);
freopen("strmatch.out", "w",stdout);
citire();
urm[0]=0;
n++;
m++;
k=0;
for(i=2;i<=n;i++)
{
while(k>0 && s[k]!=s[i-1])k=urm[k];
if (s[k]==s[i-1])k++;
urm[i]=k;
}
o=0;
for(i=0;i<m;i++){

while (o>0 && s[o]!=ss[i])o=urm[o];
if (s[o]==ss[i])o++;
if (o==n){if (ct<1000)b[++ct]=i-n+1;else ct++;}
}
printf("%d\n",ct);
if (ct>1000)ct=1000;
for(i=1;i<=ct;i++)
printf("%d ",b[i]);


return 0;
}