Cod sursa(job #2316312)

Utilizator radugnnGone Radu Mihnea radugnn Data 11 ianuarie 2019 16:11:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000010],b[2000010];
int S[1010],prefix[2000010];
int n,m,L,i,nr;
int main(){
   fin>>a+1>>b+1;
   n=strlen(a+1);
   m=strlen(b+1);
   prefix[1]=0;
   L=0;
   ///prefix
    for(i=2;i<=n;i++){
    while(L>0 && a[L+1]!=a[i])
        L=prefix[L];

    if(a[L+1]==a[i])
        L++;
    prefix[i]=L;
   }
   ///potrivire
   L=0;
   for(i=1;i<=m;i++){
    while(L>0 && a[L+1]!=b[i])
        L=prefix[L];
    if(a[L+1]==b[i])
        L++;
    if(L==n){
        nr++;
        if(nr<=1000)
            S[nr]= i-n;
        L=prefix[L];
    }
   }
   fout<<nr<<"\n";
   if(nr>1000)
    nr=1000;
   for(i=1;i<=nr;i++){
    fout<<S[i]<<" ";
   }

    return 0;
}