Cod sursa(job #2910042)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 17 iunie 2022 19:49:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int a, b, i, j, L, nr, k, v[1005];
char A[2000005], B[2000005];
int  P[2000005];
int main() {
    fin>>A+1;
    fin>>B+1;
    a=strlen(A+1);
    b=strlen(B+1);


    ///P[i]=lungimea maxima a unui subsir  al lui A ce se termina la poz i si care se regaseste si ca prefix in sirul A
    for(i=2;i<=a;i++){
        while(L && A[i]!=A[L+1]){
            L=P[L];
        }
        if(A[i]==A[L+1])
            L++;

        P[i]=L;
    }

    L=0;
    /// cautam lungimea maxima(L) a unui subsir al lui B ce se termina la pozitia i care se regaseste si ca prefix in sirul A
    /// cand o sa avem L == a atunci am gasit o solutie
    for(i=1;i<=b;i++){
        while(L && B[i]!=A[L+1]){
            L=P[L];
        }
        if(B[i]==A[L+1])
            L++;

        if(L==a){
            nr++;
            if(nr<=1000){
                v[nr]=i-a;
            }
            L=P[L];
        }

    }

    fout<<nr<<"\n";
    for(i=1;i<=min(1000, nr);i++)
        fout<<v[i]<<" ";

}