Cod sursa(job #3253567)

Utilizator Ilinca_Radu_2022Radu Ilinca-Rucsandra Ilinca_Radu_2022 Data 3 noiembrie 2024 14:07:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb
#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
int z[2*MAX+5], i, l, n;
vector<int>R;
int main()
{
    fin>>s>>t;
    t=s+'#'+t;
    n=t.size();
    z[1]=0;
    while (t[z[1]]==t[1+z[1]]) z[1]++;
    l=1;
    for (i=2; i<n; i++) {
        z[i]=max(0, min(z[i-l], l+z[l]-i));
        while (t[z[i]]==t[i+z[i]]) z[i]++;
        if (i+z[i]>l+z[l]) l=i;
    }
    for (i=1; i<n; i++) {
        if (z[i]==s.size()) R.push_back(i-s.size()-1);
    }
    fout<<R.size()<<'\n';
    for (i=0; i<min(int(R.size()), 1000); i++) {
        fout<<R[i]<<' ';
    }
    return 0;
}