Cod sursa(job #2951211)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 5 decembrie 2022 18:25:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

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

const int OUT = 1000;
const int LIM = 2e6;
string a, b;
int asize, bsize;
int lung, pref[LIM + 5];
int out, sol[OUT + 5];

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    ///il caut pe a in b
    fin>>a>>b;
    a = " " + a, asize = (int)a.size() - 1;
    b = " " + b, bsize = (int)b.size() - 1;

    lung = 0;
    pref[1] = 0;
    for(int i=2; i<=asize; i++){
        while(lung > 0 && a[lung+1] != a[i])
            lung = pref[lung];

        if(a[lung+1] == a[i])
            lung++;

        pref[i] = lung;
    }

    lung = 0;
    for(int i=1; i<=bsize; i++){
        while(lung > 0 && a[lung+1] != b[i])
            lung = pref[lung];

        if(a[lung+1] == b[i])
            lung++;

        if(lung == asize){
            out++;
            if(out <= OUT)
                sol[out] = i - lung;
        }
    }

    fout<<out<<"\n";
    for(int i=1; i<=min(out, OUT); i++)
        fout<<sol[i]<<" ";
    return 0;
}