結果
| 問題 |
No.1192 半部分列
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:02:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,632 bytes |
| コンパイル時間 | 1,191 ms |
| コンパイル使用メモリ | 112,828 KB |
| 実行使用メモリ | 228,488 KB |
| 最終ジャッジ日時 | 2025-05-14 13:04:21 |
| 合計ジャッジ時間 | 7,193 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 WA * 1 TLE * 1 -- * 14 |
ソースコード
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map> // Using unordered_map for visited set for potentially better average performance
#include <algorithm>
#include <functional> // For std::hash
using namespace std;
// Custom hash function for pairs of integers to be used with unordered_map
// This implementation uses a combination method similar to what's found in Boost libraries.
struct pair_hash {
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2>& pair) const {
// Hash the first element
auto hash1 = std::hash<T1>{}(pair.first);
// Hash the second element
auto hash2 = std::hash<T2>{}(pair.second);
// Combine the two hashes into a single hash value.
// The constants and bit shifts are common techniques to improve hash distribution.
size_t seed = 0;
// Combine hash1 into seed
seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// Combine hash2 into seed
seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
// Function to precompute the next occurrence indices for a given string `s`.
// `next_idx[i][c]` will store the minimum index `j >= i` such that `s[j] == c + 'a'`.
// If character `c` is not found at or after index `i`, it stores `len` (string length).
// This allows O(1) lookup for the next character position.
vector<vector<int>> build_next_char(const string& s, int len) {
// Initialize the table with the sentinel value `len`, indicating "not found".
// Table dimensions: (length + 1) x 26 (for each character 'a' through 'z').
vector<vector<int>> next_idx(len + 1, vector<int>(26, len));
// Iterate backwards through the string.
// This allows propagating the next occurrence information efficiently.
for (int i = len - 1; i >= 0; --i) {
// Copy the 'next occurrence' information from the state corresponding to index `i+1`.
// This handles cases where the character `s[i]` is not the one we're looking for.
for (int c = 0; c < 26; ++c) {
next_idx[i][c] = next_idx[i + 1][c];
}
// Update the entry for the character `s[i]`. The first occurrence at or after `i`
// is at index `i` itself.
next_idx[i][s[i] - 'a'] = i;
}
// The table `next_idx` is now populated.
return next_idx;
}
// State structure to be stored in the priority queue.
// Represents a state in the Dijkstra-like search.
struct State {
int idx_s; // The index in string S reached after matching the last character of `current_w`.
int idx_t; // The index in string T reached after matching the last character of `current_w`.
string current_w; // The subsequence string constructed so far to reach this state.
// Custom comparison operator for the priority queue.
// We want a min-heap based on lexicographical order of `current_w`.
// `std::priority_queue` is a max-heap by default. Using `std::greater<State>`
// reverses the comparison, effectively making it a min-heap based on this operator.
// Standard string comparison (`>`) provides lexicographical comparison.
bool operator>(const State& other) const {
return current_w > other.current_w;
}
};
// Use unordered_map to keep track of visited states (pairs of indices).
// The key is `pair<int, int>` representing (idx_s, idx_t).
// The value is `bool` (true if visited). Using `pair_hash` for hashing the pair keys.
unordered_map<pair<int, int>, bool, pair_hash> visited;
int main() {
// Optimize C++ standard streams I/O operations.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s, t;
cin >> s >> t;
int n = s.length();
int m = t.length();
// Precompute the next character occurrence tables for both strings S and T.
vector<vector<int>> next_s = build_next_char(s, n);
vector<vector<int>> next_t = build_next_char(t, m);
// Initialize the priority queue. It stores `State` objects and orders them
// using the custom comparator (`operator>`) via `std::greater<State>`, ensuring
// the state with the lexicographically smallest string is always at the top.
priority_queue<State, vector<State>, greater<State>> pq;
// Push the initial state onto the priority queue.
// Indices -1 indicate we are "before the start" of both strings.
// The initial subsequence string is empty.
pq.push({-1, -1, ""});
// Main loop of the Dijkstra-like search. Continues as long as there are states to explore.
while (!pq.empty()) {
// Retrieve the state with the lexicographically smallest string from the top of the queue.
State current = pq.top();
pq.pop();
int idx_s = current.idx_s;
int idx_t = current.idx_t;
// Create a pair representing the current state's indices.
pair<int, int> state_pair = {idx_s, idx_t};
// Check if this state (defined by the pair of indices) has already been visited.
// The `visited` map ensures we process each `(idx_s, idx_t)` pair only once,
// specifically when reached via the lexicographically smallest path (string).
if (visited.count(state_pair)) {
continue; // If visited, skip this state; a better path was already found.
}
// Mark the current state as visited.
visited[state_pair] = true;
// Try appending each character 'a' through 'z' to the current subsequence string.
for (char c_char = 'a'; c_char <= 'z'; ++c_char) {
int c = c_char - 'a'; // Convert character to integer index 0-25.
// Find the index of the next occurrence of character `c` in string S, after `idx_s`.
int next_idx_s_val;
if (idx_s == -1) { // If at the start, look from index 0.
next_idx_s_val = next_s[0][c];
} else { // Otherwise, look from the index immediately after `idx_s`.
next_idx_s_val = next_s[idx_s + 1][c];
}
// If `next_idx_s_val == n`, character `c` was not found in S after `idx_s`.
// Cannot extend with this character. Continue to the next character.
if (next_idx_s_val == n) {
continue;
}
// Find the index of the next occurrence of character `c` in string T, after `idx_t`.
int next_idx_t_val;
if (idx_t == -1) { // If at the start, look from index 0.
next_idx_t_val = next_t[0][c];
} else { // Otherwise, look from the index immediately after `idx_t`.
next_idx_t_val = next_t[idx_t + 1][c];
}
// Check if character `c` was found in S but NOT found in T (index is sentinel `m`).
if (next_idx_t_val == m) {
// We found a string `current.current_w + c_char` that satisfies the conditions:
// 1. It's a subsequence of S (because `next_idx_s_val` was valid).
// 2. It's NOT a subsequence of T (because `next_idx_t_val` was sentinel `m`).
// Since Dijkstra explores states in lexicographical order of the path string,
// this must be the lexicographically smallest such string.
// Print the resulting string and terminate the program.
cout << current.current_w + c_char << "\n";
return 0;
}
// If character `c` was found in both S and T.
// The next state corresponds to the pair of indices `(next_idx_s_val, next_idx_t_val)`.
pair<int, int> next_state_pair = {next_idx_s_val, next_idx_t_val};
// Check if this next state `(next_idx_s_val, next_idx_t_val)` has been visited.
if (!visited.count(next_state_pair)) {
// If not visited, push the new state onto the priority queue.
// The new state includes the updated indices and the extended string.
// Note: `current.current_w + c_char` creates a new string object.
// This string copying might be a performance bottleneck for very long strings/paths.
pq.push({next_idx_s_val, next_idx_t_val, current.current_w + c_char});
}
}
}
// If the loop finishes without finding a solution (priority queue becomes empty),
// it means every subsequence of S is also a subsequence of T.
// In this case, output -1 as required.
cout << -1 << "\n";
return 0;
}