Cod sursa(job #1740426)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 11 august 2016 16:25:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 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=0,i;
    potrivire[1]=0;
    for (i=2;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);
   for (i=n;i>=1;i--)
     a[i]=a[i-1];
   for (i=m;i>=1;i--)
     b[i]=b[i-1];
   pi();
   k=0;
   for (i=1;i<=m;i++){
      while(k>0 && a[k+1]!=b[i]) k=potrivire[k];
      if (a[k+1]==b[i]) k++;
      if (k==n){
         k=potrivire[n];
         nr++;
         if (nr<=1000) coada[nr]=i-n;
      }
   }
   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;
}