Cod sursa(job #165650)

Utilizator MciprianMMciprianM MciprianM Data 26 martie 2008 14:43:01
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include<stdio.h>   
using namespace std;   
char a[2000002], b[2000002];   
int m, n, lim, r[1024], pi[2000002];   
void prefix(){   
  int i, k;   
  pi[1]=0;   
  k=0;   
  for(i=2;i<=m;i++){   
    while(k && a[i]!=a[k+1])   
      k=pi[k];   
    if(a[i]==a[k+1])   
      k++;   
    pi[k]=k;   
  }   
}   
void match(){   
  int i, k;   
  k=0;   
  for(i=1;i<=n;i++){   
    while(k && a[k+1]!=b[i])   
      k=pi[k];   
    if(a[k+1]==b[i])   
      k++;   
    if(k==m)   
    {   
      lim++;   
      k=pi[k];   
      if(lim<1001)  r[lim]=i-m+1;   
    }   
  }   
}   
  
int main(){   
  int i;
  freopen("strmatch.in","r", stdin);   
  fgets(a, sizeof(a), stdin);      
  fgets(b, sizeof(b), stdin);    
  fclose(stdin);   
  for(n=0;b[n]<='Z'&&b[n]>='A'||b[n]<='z'&&b[n]>='a'||b[n]<='9'&&b[n]>='0';n++);
  for(m=0;a[m]<='Z'&&a[m]>='A'||a[m]<='z'&&a[m]>='a'||a[m]<='9'&&a[m]>='0';m++);
  for(i=m;i>0;i--)
    a[i]=a[i-1];
  a[m+1]=0;
  for(i=n;i>0;i--)
    b[i]=b[i-1];
  b[n+1]=0;
  prefix();   
  match();   
  freopen("strmatch.out","w",stdout);   
  printf("%d\n",lim);   
  int  min;   
  min=(1000<lim)?1001:(lim+1);   
  for(i=1;i<min;i++)   
    printf("%d ",r[i]);   
  fclose(stdout);   
  return 0;   
}