Cod sursa(job #1248304)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 24 octombrie 2014 21:38:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <cstdio>
#define maxl 2000010
#include <cstring>
#include <queue>
#include <ctype.h>
#include <utility>

using namespace std;

char a[maxl],b[maxl];
long p[maxl];
queue <long> qu;
long apn=0;
long la,lb;
long res[maxl];

void start(){

  long k=0;
  p[0]=0;

  for(long i=2;i<=la;i++){
     while(k&&(a[k+1]!=a[i]))
        k=p[k];
     if(a[k+1]==a[i])
        ++k;
     p[i]=k;
  }
}

void solve(){


  long k=0;
  start();

  for(long i=1;i<=lb;i++){
    while(k&&(a[k+1]!=b[i]))
         k=p[k];
    if(a[k+1]==b[i])
        ++k;
    if(k==la){
        apn++;
        if(apn<1000)
          res[apn]=i-k;
        k=p[k];
    }
  }
}

void print(){
  printf("%ld\n",apn);
  if(apn>1000)
     apn=1000;
  for(long i=1;i<=apn;i++)
     printf("%ld ",res[i]);
}

void mvstr(char x[],long a){
   long i;
   for(i=a;i>0;i--)
       x[i]=x[i-1];
}

int main(void){
  freopen("strmatch.in","r",stdin);
  freopen("strmatch.out","w",stdout);

  fgets(a,sizeof(a),stdin);
  fgets(b,sizeof(b),stdin);


     la=strlen(a)-1;
     lb=strlen(b)-1;

  mvstr(a,la);
  mvstr(b,lb);

  solve();
  print();
}