Cod sursa(job #1248345)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 24 octombrie 2014 22:45:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#define maxl 2000005
#include <cstring>
#include <queue>
#include <ctype.h>

using namespace std;

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

void start(){

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

  for(long 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 long k=0;
  start();

  for(long 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)
          qu.push(i-la);
        k=p[k];
    }
  }
}

void print(){
  printf("%lld\n",apn);

  while(!qu.empty()){
     printf("%lld ",qu.front());
     qu.pop();
  }
  printf("\n");
}

void mvstr(char x[],long long a){
   long 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;
  for(la=0;(a[la]>='a' && a[la]<='z')||(a[la]>='A' && a[la]<='Z')||(a[la]>='0' && a[la]<='9');++la);
  for(lb=0;(b[lb]>='a' && b[lb]<='z')||(b[lb]>='A' && b[lb]<='Z')||(b[lb]>='0' && b[lb]<='9');++lb);

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

  solve();
  print();
}