Cod sursa(job #3258593)

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

const int szmax = 2000000;

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

void precompute()
{
    int l = 0;
    for(int i=2;i<pat.size();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;
    fin>>s;

    pat='#' + pat;
    s='#' + s;

    precompute();
    int l=0;
    for(int i=1;i<s.size();i++){

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