Cod sursa(job #3321095)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 8 noiembrie 2025 10:34:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, t;
int n, m, i;
vector<int> rasp;

int lps[4000002];
static inline void Precalc() {
    int j = 0;
    for(int i = 1; i < n; i++) {
        while(0 < j && t[i] != t[j]) j = lps[j - 1];
        if(t[i] == t[j]) j++;
        lps[i] = j;
    }
}

int main() {
    fin.tie(NULL);
    fout.tie(NULL);
    
    fin >> s >> t;
    
    t = s + "#" + t;
    
    n = t.size();
    m = s.size();
    Precalc();

    for(i = 0; i < n; i++) {
        //cout << lps[i] << " ";
        if(m == lps[i]) {
            rasp.push_back(i - m);
        }
    }
    
    fout << rasp.size() << "\n";
    for(i = 0; i < 1000 && i < rasp.size(); i++) {
        fout << rasp[i] - m << " ";
    }
    
    return 0;
}