Cod sursa(job #3310907)

Utilizator andiRTanasescu Andrei-Rares andiR Data 17 septembrie 2025 19:59:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int Nmax=2e6+5;

string s, t, S;

int cnt;

int nrsol;
int sol[Nmax];

int pi[Nmax*2+1];

int main(){

    fin>>t>>s;

    S=t+'#'+s; // t1 t2 t3 .. tn # s1 s2 s3 ... sm

    // construim pi

    pi[0]=0;

    int n=S.size();
    for (int i=1; i<n; i++){
        int j=pi[i-1];
        while (j>0 && S[i]!=S[j])
            j=pi[j-1];

        if (S[i] == S[j])
            j++;

        pi[i]=j;
    }

    for (int i=0; i<n; i++)
        if (pi[i]==t.size())
            sol[nrsol++]=i-2*t.size();
        
    fout<<nrsol<<'\n';
    for (int i=0; i<min(nrsol, 1000); i++)
        fout<<sol[i]<<' ';

    return 0;
}