String Reconstruction
發布時間: July 12, 2017, 11:34 p.m. 最後更新時間: Sept. 15, 2023, 1:52 p.m. 時間限制: 2000ms 記憶體限制: 512M
有一字串 s 是你要重組出來的。你知道這個字串的某些部份，即你知道字串 t_i 在這個字串 s 中會出現的 k_i 個位置，分別為 x_i_1, x_i_2, x_i_3, ..., x_i_k-1, x_i_k。你知道有 n 個這種字串。你要根據這些線索，找出所有可能的 s 中字典序最小的一個答案。答案永遠存在。
1 <= n <= 10^5
所有字串 t_i 長度之和不超過 10^6
1 <= x_i_j <= 10^6
1 <= k_i <= 10^6
找出所有可能的 s 中字典序最小的一個答案。
複製範例
3 a 4 1 3 5 7 ab 2 1 5 ca 1 4
abacaba
複製範例
1 a 1 3
aaa
複製範例
3 ab 1 1 aba 1 3 ab 2 3 5
ababab
