Cod sursa(job #3345781)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 11 martie 2026 09:10:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>

#include <string>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int nmax = 4e6 + 4;
string line0, line1, str;

int n, zfunction[nmax + 2];
int where[nmax + 2];

void computezfunc(string &str){
    zfunction[1] = 0;
    int st = 1, dr = 1;

    for(int i = 2; i <= n; i++){
        zfunction[i] = max(0, min(zfunction[i - st + 1], dr - i + 1));
        for(; str[i + zfunction[i]] == str[zfunction[i] + 1]; ){
            zfunction[i]++;
            dr = i + zfunction[i] - 1;
            st = i;
        }
    }
    return;
}

int main(){

    in>>line0>>line1;
    str = '#' + line0 + '&' + line1 + '#';
    n = str.size() - 2; ///border char

    computezfunc(str);

    int ways = 0;
    for(int i = line0.size() + 2; i <= n; i++){
        if(zfunction[i] >= line0.size()){
            where[++where[0]] = i - line0.size() - 2;
        }
    }
    out<<where[0]<<"\n";
    for(int i = 1; i <= min(where[0], 1000); i++){
        out<<where[i]<<" ";
    }; out<<"\n";

    return 0;
}