Cod sursa(job #1538480)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 29 noiembrie 2015 09:31:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#define maxl 2000005
#include <cstring>
#define maxp 1000
using namespace std;

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

void prefixb();
void KMP();

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);
  prefixb();
  KMP();
  return 0;
}
void prefixb(){
  int k=0;
  //prefix[1]=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,i;
  for(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<=maxp)pos[res]=i-n+1;
     }
  }
  printf("%d\n",res);
  if(res>maxp)res=maxp;
  for(i=1;i<=res;i++)printf("%d ",pos[i]);
}