Cod sursa(job #3321435)

Utilizator PetreIonutPetre Ionut PetreIonut Data 9 noiembrie 2025 14:56:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define NMAX 2000005 
#define ll long long

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

using namespace std;

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

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

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

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