結果
| 問題 |
No.1909 Detect from Substrings
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:09:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,880 bytes |
| コンパイル時間 | 1,628 ms |
| コンパイル使用メモリ | 111,148 KB |
| 実行使用メモリ | 238,072 KB |
| 最終ジャッジ日時 | 2025-05-14 13:10:24 |
| 合計ジャッジ時間 | 6,044 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 1 TLE * 2 -- * 33 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map> // Using unordered_map for potentially better performance
#include <unordered_set> // Using unordered_set for potentially better performance
#include <utility> // For std::pair
#include <functional> // For std::hash
using namespace std;
// Use long long for hash values to avoid overflow with large moduli
typedef long long ll;
// Define two large prime moduli for double hashing. This reduces collision probability.
const ll P1 = 1e9 + 7;
const ll P2 = 1e9 + 9;
// Define two bases for the polynomial rolling hash. Small prime bases are common.
// Using different bases for the two hash functions further reduces collisions.
ll B1 = 31;
ll B2 = 37;
// Function for modular exponentiation (calculates base^exp % modulus)
// Used to compute powers of bases B1 and B2 efficiently.
ll power(ll base, ll exp, ll modulus) {
ll res = 1;
base %= modulus;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % modulus; // If exponent is odd, multiply result with base
base = (base * base) % modulus; // Square the base
exp /= 2; // Halve the exponent
}
return res;
}
// Precompute powers of bases B1 and B2 up to max_len.
// This allows O(1) lookup for B^k needed in hash calculations.
vector<ll> B1_pow, B2_pow;
void precompute_powers(int max_len) {
B1_pow.resize(max_len + 1);
B2_pow.resize(max_len + 1);
B1_pow[0] = 1; // B^0 = 1
B2_pow[0] = 1;
for (int i = 1; i <= max_len; ++i) {
B1_pow[i] = (B1_pow[i - 1] * B1) % P1; // B^i = B^{i-1} * B
B2_pow[i] = (B2_pow[i - 1] * B2) % P2;
}
}
// Structure to compute and store prefix hashes for a given string `s`.
// This allows efficient calculation of substring hashes.
struct PrefixHashes {
vector<ll> h1, h2; // Store prefix hashes for both hash functions
int len; // Length of the string
PrefixHashes(const string& s) {
len = s.length();
h1.resize(len + 1, 0); // h1[i] stores hash of s[0..i-1] (or s[1..i] if 1-indexed)
h2.resize(len + 1, 0);
for (int i = 0; i < len; ++i) {
// Calculate prefix hash iteratively: H(S[1..i]) = H(S[1..i-1]) * B + val(S[i])
// Using 1-based character values ('a' -> 1, 'b' -> 2, ...) avoids issues with character 'a' mapping to 0.
h1[i + 1] = (h1[i] * B1 + (s[i] - 'a' + 1)) % P1;
h2[i + 1] = (h2[i] * B2 + (s[i] - 'a' + 1)) % P2;
}
}
// Get hash of the suffix starting at index k (1-based index). S[k..len]
pair<ll, ll> get_suffix_hash(int k) {
if (k > len) return {0, 0}; // If k is out of bounds, suffix is empty, hash is 0.
ll suffix_len = len - k + 1;
// Calculate hash of substring S[k..len] using prefix hashes:
// H(S[k..len]) = (H(S[1..len]) - H(S[1..k-1]) * B^{len - k + 1}) mod P
// Need careful modular subtraction: (a - b + P) % P to handle potential negative results.
ll H1 = (h1[len] - (h1[k - 1] * B1_pow[suffix_len]) % P1 + P1) % P1;
ll H2 = (h2[len] - (h2[k - 1] * B2_pow[suffix_len]) % P2 + P2) % P2;
return {H1, H2};
}
// Get hash of the prefix ending at index k-1 (1-based index). S[1..k-1]
pair<ll, ll> get_prefix_hash(int k_minus_1) {
// Accessing h1[k-1], h2[k-1] directly gives hash of S[1..k-1].
// If k=1, k_minus_1=0. Returns {h1[0], h2[0]} = {0, 0}, correct for empty prefix.
return {h1[k_minus_1], h2[k_minus_1]};
}
};
// Custom hash function for pairs of long longs, needed for unordered_map/set keys.
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Combine the two hash values. A common method used in Boost library.
// Simple XOR `h1 ^ h2` might have higher collision rates.
return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
}
};
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M;
cin >> N >> M; // Read number of strings N and length M
vector<string> S(N);
for (int i = 0; i < N; ++i) {
cin >> S[i]; // Read the N strings
}
// Precompute powers of bases up to M+1, as the target string T has length M+1.
precompute_powers(M + 1);
// Map to store counts of each generated hash pair (representing a unique string T).
// Key: pair of hash values (h1, h2). Value: count of how many S_i generated this T.
unordered_map<pair<ll, ll>, int, pair_hash> counts;
// Process each input string S_i
for (int i = 0; i < N; ++i) {
PrefixHashes ph(S[i]); // Compute prefix hashes for S_i
// Set to keep track of hash pairs generated from the current S_i.
// This ensures that if multiple insertions into S_i produce the same T,
// we only increment the count for T once for this S_i.
unordered_set<pair<ll, ll>, pair_hash> visited_hashes;
// Iterate through all possible insertion positions k (1 to M+1)
// k=1 means insert before the first character. k=M+1 means insert after the last character.
for (int k = 1; k <= M + 1; ++k) {
// Iterate through all possible characters 'a' through 'z' to insert
for (char c = 'a'; c <= 'z'; ++c) {
int char_val = c - 'a' + 1; // 1-based value for the character
// Get hash of prefix S[1..k-1] (denoted P)
pair<ll, ll> prefix_hash = ph.get_prefix_hash(k - 1);
// Get hash of suffix S[k..M] (denoted S')
pair<ll, ll> suffix_hash = ph.get_suffix_hash(k);
ll H1_prefix = prefix_hash.first;
ll H2_prefix = prefix_hash.second;
ll H1_suffix = suffix_hash.first;
ll H2_suffix = suffix_hash.second;
// Calculate length of the suffix S'. If k=M+1, suffix is empty, length is 0.
int suffix_len = M - k + 1;
// Calculate hash of the string T formed by inserting c at position k: T = P c S'
// Use formula: H(T) = ( H(P c) * B^{|S'|} + H(S') ) mod P
// First calculate H(P c) = ( H(P) * B + val(c) ) mod P
ll H1_Pc = (H1_prefix * B1 + char_val) % P1;
ll H2_Pc = (H2_prefix * B2 + char_val) % P2;
// Then combine H(Pc) with H(S')
ll final_H1 = (H1_Pc * B1_pow[suffix_len] + H1_suffix) % P1;
ll final_H2 = (H2_Pc * B2_pow[suffix_len] + H2_suffix) % P2;
// The resulting hash pair for string T
pair<ll, ll> current_hash = {final_H1, final_H2};
// Check if this hash pair has already been generated from the current S_i
if (visited_hashes.find(current_hash) == visited_hashes.end()) {
// If not visited for S_i, increment its count in the global map
counts[current_hash]++;
// Mark this hash pair as visited for the current S_i
visited_hashes.insert(current_hash);
}
}
}
}
int ans = 0; // Initialize the answer counter
// Iterate through the map of hash counts
for (auto const& [hash_pair, count] : counts) {
// If a hash pair (representing a string T) has a count equal to N,
// it means T was generated from all N input strings S_i.
// Such T is a valid solution.
if (count == N) {
ans++; // Increment the answer count
}
}
// Output the final count of valid T strings
cout << ans << endl;
return 0;
}