Cod sursa(job #718430)

Utilizator mariacMaria Constantin mariac Data 20 martie 2012 19:47:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int urm[2000000],m,n,i,j;
char a[2000000],b[2000000];
void form(){urm[0]=-1;
            for(i=0,j=-1;i<m;i++,j++,urm[i]=j)
               while(j>=0&&a[i]!=a[j])
                     j=urm[j];
           }
int sol[2000000];
int main()
{fin.getline(a,2000000);
 fin.getline(b,2000000);
 int k=0;
 m=strlen(a);
 n=strlen(b);
 form();
 for(i=0,j=0;i<n;i++,j++)
     {while(j>=0&&a[j]!=b[i])
          j=urm[j];
      if(j==m-1){if(k<1000)sol[++k]=i-m+1;
                     else ++k;
                j=urm[j];}
     }
fout<<k<<"\n";
 for(i=1;i<=k&&i<=1000;i++)
     fout<<sol[i]<<" ";
    return 0;
}