Cod sursa(job #3354003)

Utilizator mariusharabariMarius Harabari mariusharabari Data 13 mai 2026 14:37:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX=2e6+1;
string a, b;
int p[NMAX], n, m;

void prefix(){
    int q=0;
    for(int i=2;i<m;i++){
        while(q>0&&a[i]!=a[q+1])
            q=p[q];
        if(a[i]==a[q+1])
            q++;

        p[i]=q;
        //cout<<i<<' '<<q<<'\n';
    }
}
int main(){
    fin>>a>>b;
    a=" "+a;
    m=a.size();
    b=" "+b;
    n=b.size();

    prefix();

    int q=0;
    int rez=0;
    vector <int> poz;
    for(int i=1;i<n;i++){
        while(q>0&&b[i]!=a[q+1])
            q=p[q];
        if(b[i]==a[q+1])
            q++;

        //cout<<i<<' '<<q<<'\n';
        if(q==m-1){
            rez++;
            if(rez<=1000)
                poz.push_back(i-m+1);
        }
    }

    fout<<rez<<'\n';
    for(int a : poz)
        fout<<a<<' ';
    return 0;
}