Cod sursa(job #3261067)

Utilizator AdrianRosuRosu Adrian Andrei AdrianRosu Data 4 decembrie 2024 13:16:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define DIM 2000001

using namespace std;

ifstream fin("strmatch.in");

ofstream fout("strmatch.out");

vector <int> sol;

int pi[DIM];

int i, j;

string a, b;

void Build_LPS(){

    for(i=1;i<a.size();i++){

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

            j = pi[j - 1];

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

            ++j;

        pi[i] = j;

    }

}

void Compute_Matches(){

    j = 0;

    for(i=0;i<b.size();i++){

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

            j = pi[j - 1];

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

            ++j;

        if(j == a.size()){

            if(sol.size() < 1000)

                sol.push_back(i - a.size() + 1);

            else return ;

            j = pi[j - 1];

        }

    }

}

int main(){

    fin >> a >> b;

    Build_LPS();

    Compute_Matches();

    assert(sol.size() == 1000);

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

    for(auto k : sol)

        fout << k << " ";

}