Cod sursa(job #3321082)

Utilizator Karan_Stefan_SanalpKaran Stefan Sanalp Karan_Stefan_Sanalp Data 8 noiembrie 2025 10:23:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int sol[1005],cnt,LPS[2000005];
void prefixsufix(string S){
    int M=S.size();
    int lg=0,i=1;
    while(i<M){
        if(S[lg]==S[i]) {lg++;LPS[i]=lg;i++;}
        else if(lg) lg=LPS[lg-1];
        else {LPS[i]=0;i++;}
    }
    
}
void KMP(string T,string S){
    int N=T.size(),M=S.size(),lg=0,i=0;
    while(i<N){
        if(T[i]==S[lg]){lg++;i++;if(lg==M){cnt++;if(cnt<=1000) sol[cnt]=i-M;lg=LPS[lg-1];}}
        else if(lg) lg=LPS[lg-1];
        else i++;
    }
}
string S,T;

int main()
{   fin>>S>>T;
    prefixsufix(S);
    KMP(T,S);
    fout<<cnt<<"\n";
    for(int i=1;i<=min(1000,cnt);i++) fout<<sol[i]<<" ";
    

    return 0;
}