Cod sursa(job #165015)

Utilizator MciprianMMciprianM MciprianM Data 25 martie 2008 08:37:54
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
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(){
  ifstream f("strmatch.in");
  f>>(a+1)>>(b+1);
  f.close();
  n=1;while(b[n]) n++; n--;
  m=1; while(a[m]) m++; m--;
  prefix();
  match();
  ofstream g("strmatch.out");
  g<<lim<<'\n';
  int i, min;
  min=(1000<lim)?1001:(lim+1);
  for(i=1;i<min;i++)
    g<<r[i]<<' ';
  g.close();
  return 0;
}