Cod sursa(job #3341981)

Utilizator bogdan_barnaBogdan Barna bogdan_barna Data 22 februarie 2026 12:17:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN=2000001;
int pi[MAXN];

void calcul(const string& A )
{
    int n=A.length();
    pi[0]=0;
    int k=0;
    for(int i=1; i<n; i++)
    {
        while(k>0 && A[k]!=A[i])
        {
            k=pi[k-1];
        }
        if(A[k]==A[i])
        {
            k++;
        }
        pi[i]=k;
    }
}

int main () 
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    string A,B;
    cin>>A>>B;
    int n=A.length();
    int m=B.length();
    calcul(A);
    vector<int> rez;
    int k=0;
    for(int i=0; i<max(m,n);i++)
    {
        while(k>0 && A[k]!=B[i])
        {
            k=pi[k-1];
        }
        if(A[k]==B[i])
        {
            k++;
        }
        if(k==n)
        {
            rez.push_back(i-n+1);
            k=pi[k-1];
        }
    }
    cout<<rez.size()<<'\n';
    for(int it:rez)
    {
        cout<<it<<" ";
    }
}