Cod sursa(job #721313)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 23 martie 2012 16:24:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstring>
#include <vector>
#include <fstream>
#define nmax 2000010

using namespace std;

int F[nmax];
char pattern[nmax];
char sir[nmax];

int main(){
  ifstream fin("strmatch.in");
  fin>>pattern;
  fin>>sir;
  int i,j;
  int m=strlen(pattern);
  int n=strlen(sir);
  //construiesc functia de esec
  F[0]=0;
  F[1]=0;
  for(i=2;i<=m;i++){
    j=F[i-1];
    while(1){
     if(pattern[j]==pattern[i-1]){
       F[i]=j+1;break;
     }
     if(j==0){
       F[i]=0;
       break;
     }
    j=F[j];
    }
 }   
 //afisez
 /*for(i=0;i<=m;i++)
   cout<<F[i]<<" ";
 cout<<endl;*/
 //KMP
 i=0;
 j=0;
 vector <int> buffer;
 while(1){
   if(j==n)break;
   if(sir[j]==pattern[i]){
     i++;
     j++;
     if(i==m){
       //cout<<j-m<<" ";
       buffer.push_back(j-m);
     }
   }else if(i>0)i=F[i];
             else j++;
 }
 ofstream fout("strmatch.out");
 fout<<buffer.size()<<endl;
 for(i=0;i<buffer.size();i++)
   fout<<buffer[i]<<" ";
 fout<<endl;
return 0;
}