Cod sursa(job #1535550)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 24 noiembrie 2015 22:02:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#define maxl 2000005
#include <cstring>

using namespace std;

char M[maxl],N[maxl];
int n,m,prefix[maxl];
int res=0,pos[maxl];

void citeste();
void calculeaza_prefix();
void KMP();
void Scrie();

int main(){
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 citeste();
 calculeaza_prefix();
 KMP();
 Scrie();
    return 0;
}
void citeste(){
  N[0]=M[0]=' ';
  scanf("%s",N+1);n=strlen(N);
  scanf("%s",M+1);m=strlen(M);
}
void calculeaza_prefix(){
  int k=0;
  for(int i=2;i<n;i++){
      while(k && N[k+1]!=N[i])k=prefix[k];
      if(N[k+1]==N[i])k++;
      prefix[i] = k;
  }
}
void KMP(){
  int k=0;
  for(int i=1;i<m;i++){
     while(k && N[k+1]!=M[i])k=prefix[k];
     if(N[k+1]==M[i])k++;
     if(k==n-1){
       res++;
       if(res<=1000)pos[res]=i-n+1;
     }
  }
}

void Scrie(){
  printf("%d\n",res);
  if(res>1000)res=1000;
  for(int i=1;i<=res;i++)printf("%d ",pos[i]);
  printf("\n");
}