Cod sursa(job #3142244)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 20 iulie 2023 12:23:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int i, j, n, m, a, b, L, nr;
char A[2000002], B[2000002];
char C[2000002], D[2000002];
int v[1002], P[2000002];
int main() {
    cin>>C;
    cin>>D;
    strcpy(A+1, C);
    strcpy(B+1, D);
    a=strlen(A+1);
    b=strlen(B+1);
    L=0;
    for(i=2;i<=a;i++){
        while(L && A[L+1]!=A[i])
            L=P[L];
        if(A[L+1]==A[i])
            L++;
        P[i]=L;
    }
    /*
    for(i=1;i<=a;i++){
        cout<<P[i]<<" ";
    }
    */
    L=0;
    for(i=1;i<=b;i++){
        while(L && A[L+1]!=B[i])
            L=P[L];
        if(A[L+1]==B[i])
            L++;
       // cout<<i<<" "<<L<<"\n";
        if(L==a){
            nr++;
            if(nr<=1000)
                v[nr]=i-L;
        }
    }
    cout<<nr<<"\n";
    for(i=1;i<=min(nr, 1000);i++)
        cout<<v[i]<<" ";


}