Pagini recente » Cod sursa (job #3256201) | Cod sursa (job #300554) | Cod sursa (job #1319851) | Cod sursa (job #2412033) | Cod sursa (job #3142550)
#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;
}