Cod sursa(job #3258591)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 23 noiembrie 2024 11:11:16
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int szmax = 2000000;

char s[szmax + 5];
char pat[szmax + 5];
int pr[szmax + 5];
int psz;
vector <int> sol;

void precompute()
{
    int l = 0;
    for(int i=2;pat[i];i++)
    {
        psz=i;
        /// find last matching suffix
        while(l!=0 && pat[i]!=pat[l+1])
            l = pr[l];
        /// advance pattern length
        if(pat[i]==pat[l+1])
            ++l;
        pr[i] = l;
    }
}

int nrs;

int main(){
    fin>>(pat+1);
    fin>>(s+1);
    precompute();
    int l=0;
    for(int i=1;s[i];i++){

        while(l!=0 && s[i]!=pat[l+1])
            l = pr[l];
        if(s[i]==pat[l+1])
            ++l;
        if(l==psz){
            if(sol.size()<1000)
                sol.push_back(i-psz);
            nrs++;
            l=pr[l];
        }
    }
    fout<<nrs<<'\n';
    for(auto& i : sol)
        fout<<i<<' ';
}