Cod sursa(job #1210793)

Utilizator breahnadavidBreahna David breahnadavid Data 21 iulie 2014 09:22:28
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<iostream> 
#include<fstream> 
#include<string.h> 
  
using namespace std; 
  
ifstream f("strmatch.in"); 
ofstream g("strmatch.out"); 
  
int i,j,n,m,k,v[2000005],u[2000005];
char s[2000005],t[2000005]; 
  
void repetitie() 
        { 
  
        u[0]=0; 
        j=1; 
        for(i=1;i<n;i++) 
                { 
                if(s[i]==s[i-j])u[i]=i-j+1; 
                else {j=i+1;u[i]=0;} 
                } 
        } 
  
  
void parcurg() 
        { 
        if(s[0]==t[0]){v[0]=0;j=1;} 
        else {j=0;v[0]=-1;} 
        k=0; 
  
        for(i=1;i<=m&&k<1001;i++) 
                { 
                if(j==n){k++;j=u[v[i-1]];} 
                 if(s[j]==t[i]) 
                        { 
                        v[i]=v[i-1]+1; 
                        if(v[i]==n)v[i]=j; 
                        j++; 
                        } 
                 else
                        { 
                        if(s[u[v[i-1]]]==t[i]){j=u[v[i-1]];v[i]=u[v[i-1]];j++;} 
                        else {v[i]=-1;j=0;} 
                        } 
                } 
        } 
  
int main() 
{ 
f>>s; 
f>>t; 
n=strlen(s); 
m=strlen(t); 
  
repetitie(); 
parcurg(); 
  
//cout<<t<<endl; 
//for(i=0;i<m;i++)cout<<v[i]; 
//cin>>n; 
g<<k<<'\n'; 
k=0; 
for(i=0;i<m&&k<1000;i++)if(v[i]==n-1){g<<i-n+1<<' ';k++;} 
g.close(); 
return 0; 
}