Cod sursa(job #3215954)

Utilizator lolismekAlex Jerpelea lolismek Data 15 martie 2024 14:58:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define pb push_back
#define fr first
#define sc second
#define vt vector
#define ub upper_bound
#define lb lower_bound

using namespace std;

string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int NMAX = 4e6;

int kmp[NMAX + 1];

void KMP(string s){
    kmp[1] = 0;
    for(int i = 2; i < sz(s); i++){
        int l = kmp[i - 1];

        while(l > 0 && s[l + 1] != s[i]){
            l = kmp[l];
        }

        if(s[l + 1] == s[i]){
            kmp[i] = l + 1;
        }
    }
}

int main(){

    string a, b;
    fin >> a >> b;

    string s = "$" + a + "$" + b;
    KMP(s);

    int ans = 0;
    vt <int> pos;

    for(int i = sz(a) + 2; i < sz(s); i++){
        if(kmp[i] == sz(a)){
            ans++;
            if(sz(pos) <= 1000){
                pos.pb(i - 2 * sz(a) - 1);
            }
        }
    }

    fout << ans << '\n';
    for(int x : pos){
        fout << x << ' ';
    }
    fout << '\n';

    return 0;
}