Cod sursa(job #758305)

Utilizator ion824Ion Ureche ion824 Data 15 iunie 2012 09:22:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<fstream>
#include<string>
const int MAX=2000005;
using namespace std;
string a,b;
int m,n,nr,sol[1005],next[MAX];

void readdata(){
     ifstream fin("strmatch.in");
     int i; string aux;
     getline(fin,a); m=a.length();
     getline(fin,b); n=b.length();
     aux=a[m-1]; a.append(aux);
     aux=b[n-1]; b.append(aux);     
     for(i=m;i>0;--i)a[i]=a[i-1];
     for(i=n;i>0;--i)b[i]=b[i-1];
     fin.close();
     }

void make_prefix()
{
     int k=0,x;
     next[1]=0;
     for(x=2;x<=m;++x)
     {
         while(k && a[k+1]!=a[x])k=next[k]; 
         if(a[k+1]==a[x])++k;
         next[x]=k;                
     }    
}

void solve()
{
  int i,k=0;
  make_prefix();  
  for(i=1;i<=n;++i)
  {
     while(k && a[k+1]!=b[i])k=next[k]; 
     if(a[k+1]==b[i])++k;
     if(k==m)
     {
     ++nr;
     if(nr<=1000)
         sol[nr]=i-m;
     k=next[k];
     }             
  }       
}

void writedata()
{
  ofstream fout("strmatch.out");
  fout<<nr<<'\n';
  if(nr>1000)nr=1000; 
  for(int i=1;i<=nr;++i)
    fout<<sol[i]<<' ';
  fout.close();   
}

int main(void){        
    readdata();
    solve();
    writedata();
 return 0;   
}