Cod sursa(job #3348757)

Utilizator moloDaniMolodet Andrei Daniel moloDani Data 23 martie 2026 20:32:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int mxN = 2e6 + 1;

char a[mxN], b[mxN];
int lsp[mxN], lng;

void init(){
    int i = 1, j = 0;
    while(a[i] != '\0'){
        if(a[i] == a[j])
            lsp[i++] = ++j;
        else
            if(!j){
                lsp[i] = 0;
                i++;
            }else
                j = lsp[j - 1];
    }
    lng = i;
}

int main(){
    fin.getline(a, mxN);
    fin.getline(b, mxN);

    init();

    vector<int> ans;
    int i = 0, j = 0, contor = 1;
    while(b[i] != '\0'){
        if(a[j] == b[i]){
            i++;
            j++;
            if(j == lng){
                ans.push_back(i - j);
                j = lsp[lng - 1];
            }
        }else{
            if(!j)
                i++;
            else
                j = lsp[j - 1];
        }
    }

    fout << ans.size() << "\n";
    for(auto x : ans)
        if(contor++ <= 1000)
            fout << x << " ";
}