Cod sursa(job #3204448)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 16 februarie 2024 19:02:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string pat;
string txt;
string s;

int n;

long long sol;
vector <int> sol_poz;

int z[4000005];

void build()
{
    s = '0' + pat + txt;
    int st=1;
    int dr=1;
    n = s.size()-1;
    for(int i = 2;i<=n;i++)
    {
        if(i>dr)
        {
            st=i;
            dr=i;
            while(dr<=n && s[dr] == s[dr-i+1])
                dr++;
            dr--;
            z[i]=dr-st+1;
        }
        else
        {
            int nr_fr = i-st+1;
            if(z[nr_fr]<dr-i+1)
                z[i]=z[nr_fr];
            else
            {
                st=i;
                while(dr<=n && s[dr]==s[dr-i+1])
                    dr++;
                dr--;
                z[i]=dr-st+1;
            }
        }
    }
}



int main()
{
    fin>>pat>>txt;
    build();
    for(int i=pat.size()+1;i<=n;i++)
    {
        if(z[i]>=pat.size()){
            sol++;
            if(sol_poz.size()<1000)
                sol_poz.push_back(i-pat.size()-1);
        }
    }
    fout<<sol<<'\n';
    for(auto& i : sol_poz)
        fout<<i<<' ';
}