Cod sursa(job #164711)

Utilizator MciprianMMciprianM MciprianM Data 24 martie 2008 18:37:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<string.h>
using namespace std;
int pf[2000001],n,m, r[2000001], lim;
char a[2000001], b[2000001];
void KMP(){
  int k,i;
  k=0;
  for(i=1;i<=n;i++){
    while(k>0&&a[k]!=b[i-1])
      k=pf[k];
    if(a[k]==b[i-1])
      k++;
    if(k==m-1){
      r[lim++]=i-m+1;
      k=pf[k];
    }
}
}
void prefix(){
  int i, k;
  pf[1]=0;
  k=0;
  for(i=2;i<=m;i++){
    while( k>0 && a[k]!=a[i-1])
      k=pf[k];
    if(a[k]==a[i-1])
      k++;
    pf[i-1]=k;
  }
}
int main(){
  int i;
  ifstream f("strmatch.in");
  f>>a>>b;
  f.close();
  m=strlen(a);
  n=strlen(b);
  prefix();
  KMP();
  ofstream g("strmatch.out");
  g<<lim<<'\n';
  for(i=0;i<lim&&i<1000;i++)
    g<<r[i]<<' ';
  g<<'\n';
  g.close();
  return 0;
}