Cod sursa(job #3142242)

Utilizator carinamariaCarina Maria Viespescu carinamaria Data 20 iulie 2023 12:18:25
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 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];
int v[1002], P[2000002];
int main() {
    cin>>A+1;
    cin>>B+1;
    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]<<" ";


}