Cod sursa(job #3341982)

Utilizator bogdan_barnaBogdan Barna bogdan_barna Data 22 februarie 2026 12:21:38
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 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 () 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    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<m;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';
    int lim=min((int)rez.size(),1000);
    for(int i=0; i<lim;i++)
    {
        cout<<rez[i]<<" ";
    }
    cout<<'\n';
}