Cod sursa(job #2329256)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 26 ianuarie 2019 15:19:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2001100],b[2001100];
int tata[2001100];
int la,lb,i,lun,nrsol;
vector <int> sol;
int main()
{
   fin>>(a+1)>>(b+1);
   la=strlen(a+1);
   lb=strlen(b+1);
   tata[1]=0;
   for(i=2;i<=la;i++){
    while(lun!=0&&a[lun+1]!=a[i])
    lun=tata[lun];

    if(a[lun+1]==a[i])
     lun++;
    tata[i]=lun;
   }
   lun=0;
   for(i=1;i<=lb;i++){
    while(lun!=0&&a[lun+1]!=b[i])
        lun=tata[lun];
    if(a[lun+1]==b[i])
        lun++;
    if(lun==la){
        nrsol++;
        if(nrsol<=1000)
            sol.push_back(i-la);
        lun=tata[lun];
    }
   }
   fout<<nrsol<<"\n";
   for(i=0;i<sol.size();i++)
    fout<<sol[i]<<" ";
}