Cod sursa(job #1740402)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 11 august 2016 16:01:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,j,k,potrivire[2000001],nr,coada[2000001];
char a[2000001],b[2000001];
void pi(){
    int k=-1,i;
    potrivire[0]=0;
    for (i=1;i<n;i++){
        while(k>0 && a[k+1]!=a[i]) k=potrivire[k];
        if (a[k+1]==a[i]) k++;
        potrivire[i]=k;
    }
}
int main(){
   fin.get(a,2000001,'\n');
   fin.get();
   fin.get(b,2000001,'\n');
   fin.close();
   n=strlen(a);
   m=strlen(b);
   pi();
   k=-1;
   for (i=0;i<m;i++){
      while(k>0 && a[k+1]!=b[i]) k=potrivire[k];
      if (a[k+1]==b[i]) k++;
      if (k==n-1){
         nr++;
         if (nr<=1000) coada[nr]=i-n+1;
      }
   }
   fout<<nr<<'\n';
   if (nr<=1000)
     for (i=1;i<=nr;i++)
       fout<<coada[i]<<" ";
    else
        for (i=1;i<=1000;i++)
          fout<<coada[i]<<" ";
   fout.close();
   return 0;
}