You are given a string s of lowercase alphabets. Some elements of s are replaced by the character ‘?’ . You are given another string t. You need to replace all the ‘?’ in s by lowercase alphabets so as to maximize the number of occurences of t in s. The occurences of t in s may overlap. For eg if s=pqr??rpq and t=pqrpq then change s to pqrpqrpq and answer is 2. You need to print the maximum number of occurences of t in s. 1<=|s|<=10^5,1<=|t|<=10^5,1<=|s|.|t|<=10^7.
I found this problem on codeforces(808G) but i am not able to solve it. Please give a hint.