Cod sursa(job #2849589)

Utilizator florinrafiliuRafiliu Florin florinrafiliu Data 15 februarie 2022 13:09:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int maxN = 4e6 + 5;

int z[maxN];

void z_function (string s) {
    int l = 0, r = 0;
    int n = s.size();
    for(int i = 1; i < n; ++i) {
        if(i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while(i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if(i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}

int main() {

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

    string s = a + '&' + b;

    z_function(s);

    vector <int> ans;

    int cnt = 0;
    for(int i = a.size()+1; i < s.size() && cnt < 1000; ++i) {
        if(z[i] == a.size()) {
            ans.push_back(i-a.size()-1);
            cnt += 1;
        }

    }

    fout << ans.size() << "\n";

    for(int i = 0; i < ans.size(); ++i)
        fout << ans[i] << " ";

    return 0;
}