Cod sursa(job #3292391)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 8 aprilie 2025 10:56:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>
#define DIM 2000001

using namespace std;

ifstream fin("strmatch.in");

ofstream fout("strmatch.out");

string a, b;

int lps[DIM];

vector <int> ret;

int n, m, i;

void Compute_LPS(){

    int j = 0;

    for(int i=1;i<n;i++){

        while(j > 0 && a[i] != a[j])

            j = lps[j - 1];

        if(a[i] == a[j])

            ++j;

        lps[i] = j;

    }

}

void Solve(){

    int j = 0;

    for(int i=0;i<m;i++){

        while(j > 0 && b[i] != a[j])

            j = lps[j - 1];

        if(b[i] == a[j])

            ++j;

        if(j == n){

            ret.push_back(i - n + 1);

            j = lps[j - 1];

        }

    }

}

int main(){

    fin >> a >> b;

    n = a.size();

    m = b.size();

    Compute_LPS();

    Solve();

    fout << ret.size() << "\n";

    for(int i=0;i<min(1000, (int)ret.size());i++)

        fout << ret[i] << " ";

}