Cod sursa(job #3359152)

Utilizator Andrei_GAndreiG Andrei_G Data 25 iunie 2026 12:24:35
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int nmax = 2e6;

string a, b;
int n, m;

int pi[nmax + 5];

void fastio(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

void handleinput(){
    cin>>a>>b;
}

void setup(){
    n = a.size();
    m = b.size();
    for (int i = 1; i < m; i++){
        int j = pi[i - 1];
        while (j && a[j] != b[i]){
            j = pi[j - 1];
        }
        if (a[j] == b[i]){
            j++;
        }
        pi[i] = j;
    }
}

void handleoutput(){
    int rez = 0;
    for (int i = 1; i < m; i++){
        rez += (pi[i] == n) ? 1 : 0;
    }
    cout<<rez<<"\n";
    for (int i = 1; i < m; i++){
        if (pi[i] == n){
            cout<<i - n + 1<<" ";
        }
    }
}

signed main(){
    fastio();
    handleinput();
    setup();
    handleoutput();
}