Cod sursa(job #1577813)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 23 ianuarie 2016 21:16:14
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#define nmax 2000003
#include <cstring>

using namespace std;

char N[nmax],M[nmax];
int n,m,prefix[nmax],poz[nmax],rez=0;

int main(){

freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

N[0]=M[0]=' ';
scanf("%s",N+1);n = strlen(N);
scanf("%s",M+1);m = strlen(M);

int k=0,i;
for(i = 2;i < n;++i){
while(k!=0 && N[k+1]!=N[i])k = prefix[k];
if(N[i]==N[k+1])k++;
prefix[i]=k;
}

for(i = 1;i < m;++i){
while(k != 0 && M[i]!=N[k+1])k = prefix[k];
if(M[i] == N[k+1])k++;
if(k == n-1){
  rez++;
  if(rez<=1000)poz[rez] = i-n+1;
}
}

printf("%d\n",rez);
if(rez>1000)rez = 1000;
for(i = 1;i<=rez;++i)printf("%d ",poz[i]);
printf("\n");


return 0;
}