Cod sursa(job #3142550)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 22 iulie 2023 14:39:24
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.04 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

struct info {
    int first_order, second_order, org_idx;
};

/*
* Compare the pattern with the suffix that starts on the index `index` in the text T
* Returns: 0 if the suffix is equal with the pattern
*          1 if the suffix is greater than the pattern
*         -1 if the suffix is less than the pattern 
*/
int cmp(const string& T, const string& P, int index) {

    int i = index, j = 0;
    while (i < T.size() && j < P.size() && T[i] == P[j]) {
        j++, i++;
    }

    if (j == P.size())
        return 0;
    
    if (i == T.size())
        return -1;

    if (T[i] < P[j])
        return -1;
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string P, T;
    f >> P >> T;

    int n = T.size();
    int k = log2(n);

    vector<vector<int>> dp(k + 1, vector<int>(n));
    vector<info> order_suffix_index(n);

    for (int i = 0; i < n; i++)
        dp[0][i] = T[i] - '0';

    for (int j = 1; j <= k; j++) {

        for (int i = 0; i < n; i++) {
            int index_next_suffix = i + (1 << (j - 1));
            order_suffix_index[i] = { dp[j - 1][i], (index_next_suffix < n) ? dp[j - 1][index_next_suffix] : -1,
                i };
        }

        sort(order_suffix_index.begin(), order_suffix_index.end(), [&](const info& X, const info& Y) {
            if (X.first_order == Y.first_order) {
                if (X.second_order == Y.second_order)
                    return X.org_idx < Y.org_idx;
                return (X.second_order < Y.second_order);
            }

            return X.first_order < Y.first_order;
            });
       
        for (int i = 0; i < n; i++) {
            int first_order = order_suffix_index[i].first_order;
            int second_order = order_suffix_index[i].second_order;
            int org_index_suffix = order_suffix_index[i].org_idx;
            dp[j][org_index_suffix] = (i > 0 && order_suffix_index[i - 1].first_order == first_order &&
                order_suffix_index[i - 1].second_order == second_order) ? dp[j][order_suffix_index[i - 1].org_idx] : i;
        }
    }

    vector<int> ordered_suffixes;
    for (int i = 0; i < n; i++) ordered_suffixes.push_back(order_suffix_index[i].org_idx);

    //for (int i = 0; i < n; i++) {
    //    int first_order = order_suffix_index[i].first_order;
    //    int second_order = order_suffix_index[i].second_order;
    //    int org_idx = order_suffix_index[i].org_idx;

    //    string S = "";
    //    for (int j = org_idx; j < n; j++) S = S + T[j];
    //    cout << S << ' ' << i << ' ' << org_idx << ' ' << dp[k][org_idx] << '\n';
    //}

    int l = 0, r = n - 1;
    int lower_idx = -1; // first suffix that matches the pattern
    while (l <= r) {
        int mid = (l + r) / 2;
        int outcome_cmp = cmp(T, P, ordered_suffixes[mid]);
        if (outcome_cmp < 0) {
            l = mid + 1;
        }
        else
        if(outcome_cmp > 0) {
            r = mid - 1;
        }
        else
        if (outcome_cmp == 0) {
            lower_idx = mid;
            r = mid - 1;
        }
    }

    int upper_idx = -1; // last suffix that matches the pattern
    l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        int outcome_cmp = cmp(T, P, ordered_suffixes[mid]);
        if (outcome_cmp < 0) {
            l = mid + 1;
        }
        else
        if (outcome_cmp > 0) {
            r = mid - 1;
        }
        else
        if (outcome_cmp == 0) {
            upper_idx = mid;
            l = mid + 1;
        }
    }

    g << upper_idx - lower_idx + 1 << '\n';

    vector<int> ans;
    for (int i = lower_idx, j = 1000; i <= upper_idx && j > 0; i++, j--) {
        ans.push_back(ordered_suffixes[i]);
    }
    sort(ans.begin(), ans.end());

    for (int x : ans) g << x << ' ';

    return 0;
}