Codeforces Round 964 (Div. 4) D. Slavic's Exam

Title Link./contest/1999/problem/D

Title Description

Slavic has a very difficult exam and needs your help to pass. Here are the questions he is struggling with:

There exists a string s that consists of lowercase letters and possibly zero or more "?" .

Slavic was asked to change each "?" to lowercase letters, making the string t a subsequence of the string s (not necessarily consecutive).

Output any such string, or if no such string exists that matches the condition, then this is not possible

importation

The first line contains an integer T ( 1 ≤ T ≤ 104) - the number of test cases.
The first line of each test case contains a string s ( 1 ≤ |s| ≤ 2⋅105, and s consists only of lowercase letters and "?" ) - the original string.
The second line of each test case contains a string t ( 1 ≤ |t| ≤ |s|, and t consists of lowercase letters only) - this string should be a subsequence of the string s. The second line of each test case contains a string t ( 1 ≤ |t| ≤ |s|, and t consists of lowercase letters only).
The sum of |s| for all test cases does not exceed 2⋅105, where |x| denotes the length of string x.

exports

For each test case, output "NO" (without quotes) if the string described in the statement does not exist.
Otherwise, output "YES" (without quotes). Then, output one line - a string that meets all the conditions.
You can output "YES" and "NO" in any case (e.g., the strings "yEs", "yes " and "Yes" will be recognized as positive responses).
If there is more than one answer, you can output any of them.

Input Sample

5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom

Sample output

YES
xabax
YES
abcde
YES
ayyyx
NO
NO

analyze: Given two lowercase strings s and t, the characters at certain positions in s are ? which can be replaced with any lowercase character. Now you need to modify s to satisfy that t is a subsequence of s. Output the construction scheme or determine that no scheme exists.

Greedily match each bit of t from the beginning to the end of s, and the ? character is modified to be the character that t is currently matching with s. After matching, iterating over s will change the extra '? to any lowercase letter.

Greedy. Time complexity O(n).

coding

// Problem: D. Slavic's Exam
// Contest: Codeforces - Codeforces Round 964 (Div. 4)
// URL: /contest/1999/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor ()

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}
 
LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
const int Inf=0x3f3f3f3f;
const int N =1e5+10;



int Case;
void solve()
{
	string s;
	string t;
	cin>>s>>t;
	int len1=(),len2=();
	int j=0;
	for(int i=0;i<len1;i++)
	{
		if(s[i]==t[j])j++;
		if(s[i]!=t[j]&&s[i]=='?')
		{
			s[i]=t[j];
			j++;
		}
		if(j==len2)
		{   
			break;
		}
	}

	for(int i=0;i<len1;i++)if(s[i]=='?')s[i]='x';
		if(j==len2)
	{   
			cout<<"YES"<<endl<<s<<endl;
			return;
	}
	else cout<<"No"<<endl;

}


int main()
{	
	ios::sync_with_stdio(false);
    (0);
    (0);
	cin>>Case;
	while(Case--)solve();

	return 0;
}