Cod sursa(job #3321063)

Utilizator PetreIonutPetre Ionut PetreIonut Data 8 noiembrie 2025 10:07:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define NMAX 2000005
#define ll long long
#define mod 20173333

std::ifstream f("strmatch.in");
std::ofstream g("strmatch.out");

using namespace std;

int n, m, ans;
string a, b;
int lps[NMAX], sol[NMAX];

void init(){
    int i=1, lg=0;
    while(i<n){
        if(a[i]==a[lg])lg++,lps[i++]=lg;
        else{
            if(lg) lg=lps[lg-1];
            else lps[i++]=0;
        }
    }
}

void kmp(){
    int i=0, lg=0;
    while(i<m){
        if(b[i]==a[lg]){
            i++;
            lg++;
            if(lg==n)sol[++ans]=i-lg, lg=lps[lg-1];
        }
        else{
            if(lg) lg=lps[lg-1];
            else i++;
        }
        if(ans==1000) break;
    }
    g << ans << '\n';
    for(int i=1;i<=ans;i++)g << sol[i] << " ";
}

int main(){
    f >> a;
    f.get();
    f >> b;
    n=a.size(), m=b.size();
    init();
    kmp();
}