Cod sursa(job #3349838)

Utilizator eric_dragosDragos Eric eric_dragos Data 2 aprilie 2026 17:47:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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];
vector<int> poz;
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.push_back(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 << poz.size() << '\n';
    for(int i = 0; i<min((int)poz.size(),1000); i++){
        fout << poz[i] << ' ';
    }
    
    return 0;
}