Cod sursa(job #3359156)

Utilizator Andrei_GAndreiG Andrei_G Data 25 iunie 2026 12:35:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 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 = 4e6;

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();
    a = a + '#' + b;
    m += n + 1;
    for (int i = 1; i < m; i++){
        int j = pi[i - 1];
        while (j && a[j] != a[i]){
            j = pi[j - 1];
        }
        if (a[j] == a[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";
    int cnt = 0;
    for (int i = 1; i < m; i++){
        if (pi[i] == n){
            cout<<i - 2 * n<<" ";
            cnt++;
        }
        if (cnt == 1000){
            break;
        }
    }
}

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