Cod sursa(job #316594)

Utilizator mlazariLazari Mihai mlazari Data 20 mai 2009 11:18:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000003
#define min(a,b) a<b?a:b

char A[NMAX],B[NMAX];
int pi[NMAX],answ[1000],n=0,a,b;

void prefixe() {
  int i,k=0;
  pi[1]=0;
  for(i=2;i<=a;i++) {
    while((k>0)&&(A[k+1]!=A[i])) k=pi[k];
    if(A[k+1]==A[i]) k++;
    pi[i]=k;
  }
}

void KMP() {
  int q=0;
  for(int i=1;i<=b;i++) {
    while((q>0)&&(A[q+1]!=B[i])) q=pi[q];
    if(A[q+1]==B[i]) q++;
    if(q==a)
     if(n>=1000) n++;
     else answ[n++]=i-a;
  }
}

void citeste() {
  freopen("strmatch.in","r",stdin);
  fgets(A+1,sizeof(A),stdin);
  fgets(B+1,sizeof(B),stdin);
  a=strlen(A+1)-1;
  b=strlen(B+1)-1;
  fclose(stdin);
}

void scrie() {
  freopen("strmatch.out","w",stdout);
  printf("%d\n",n);
  if(n>1000) n=1000;
  for(int i=0;i<n;i++) printf("%d ",answ[i]);
  fclose(stdout);
}

int main() {
  citeste();
  prefixe();
  KMP();
  scrie();
}