Cod sursa(job #1198970)

Utilizator breahnadavidBreahna David breahnadavid Data 17 iunie 2014 19:26:58
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<iostream>
#include<fstream>
#include<math.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int i,j,n,m,k,v[2000002],u[200002];
char s[20000000],t[20000000];

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;
}