304326: CF825D. Suitable Replacement
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Suitable Replacement
题意翻译
``` 题目大意: 给出字符串s和t,字符串s中的'?'可以用字符串t中的字符代替,要求使得最后得到的字符串s(可以将s中的字符位置两两交换任意位置任意次数)中含有的子串t最多. ```题目描述
You are given two strings $ s $ and $ t $ consisting of small Latin letters, string $ s $ can also contain '?' characters. Suitability of string $ s $ is calculated by following metric: Any two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings $ s $ , you choose the one with the largest number of non-intersecting occurrences of string $ t $ . Suitability is this number of occurrences. You should replace all '?' characters with small Latin letters in such a way that the suitability of string $ s $ is maximal.输入输出格式
输入格式
The first line contains string $ s $ ( $ 1<=|s|<=10^{6} $ ). The second line contains string $ t $ ( $ 1<=|t|<=10^{6} $ ).
输出格式
Print string $ s $ with '?' replaced with small Latin letters in such a way that suitability of that string is maximal. If there are multiple strings with maximal suitability then print any of them.
输入输出样例
输入样例 #1
?aa?
ab
输出样例 #1
baab
输入样例 #2
??b?
za
输出样例 #2
azbz
输入样例 #3
abcd
abacaba
输出样例 #3
abcd