Cod sursa(job #3349833)

Utilizator eric_dragosDragos Eric eric_dragos Data 2 aprilie 2026 17:42:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
const int N = 2e6+2;
ll lps[N], cnt = 0, poz[1005];
void citire(){
    fin >> a >> b;
}
void createLps(string &b){
    ll len=0, i=1;
    lps[0] = 0;
    while(i < b.length()){
        if(b[i] == b[len]){
            lps[i++] = ++len;
        }
        else{
            if(len == 0){
                lps[i++] = 0;
            }
            else{
                len = lps[len-1];
            }
        }
    }
}

void kmp(string &txt, string &pat){
    ll i = 0, j = 0;
    ll n = txt.length();
    ll m = pat.length();
    while(i < n){
        if(txt[i] == pat[j]){
            i++;j++;
            if(j >= m){
                poz[++cnt] = i-j;
                j = lps[j-1];
            }
        }
        else{
            if(j != 0) j = lps[j-1];
            else i++;
        }
    }
}

int main(){
    citire();
    createLps(a);
    kmp(b, a);
    fout << cnt << '\n';
    for(int i = 1; i<=min(cnt,1000LL); i++){
        fout << poz[i] << ' ';
    }
    
    return 0;
}