Cod sursa(job #3345779)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 11 martie 2026 08:52:59
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 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[0] = 0;
    for(int i = 2; i <= n; i++){
        zfunction[i] = 0;
        for(; str[i + zfunction[i]] == str[zfunction[i] + 1]; ){
            zfunction[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;
}