Anthem
Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.
Though there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible.
He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.
The anthem is the string s of no more than 10^5 small Latin letters and question marks. The most glorious victory is the string t of no more than 10^5 small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string tin string s is maximal.
Note that the occurrences of string t in s can overlap. Check the third example for clarification.
Input
The first line contains string of small Latin letters and question marks s (1≤|s|≤10^5).
The second line contains string of small Latin letters t (1<|t|<10^5).
Product of lengths of strings Isl.It won't exceed 10^7.
Output
Output the maximum number of occurrences of string t you can achieve by replacing all the question marks in string s with small Latin letters.
Examples input Copy
winlose???winl???w??win
output Copy
5
Sample input
winlose???winl???w??
win
Sample output
5
Program:
def can_put(s, t, pos):
for i in range(len(t)):
if s[i + pos] != '?' and s[i + pos] != t[i]:
return False
return True
def max_occurrences(s, t):
n, m = len(s), len(t)
feasible_positions = [False] * n
# Mark all positions where t can start.
for i in range(n - m + 1):
feasible_positions[i] = can_put(s, t, i)
answer = 0
start = 0
for i in range(n):
if i - window_start + 1 > m:
if feasible_positions[start]:
answer += 1
start += 1
# Count for the trailing positions
for i in range(start, n - m + 2):
if feasible_positions[i]:
answer += 1
return answer
if __name__ == "__main__":
s = input().strip()
t = input().strip()
print(max_occurrences(s, t))
Explanation:
Understanding the Algorithm to Maximize String Occurrences
If you've ever faced the challenge of counting the maximum number of times a substring can appear in another string after certain modifications, this guide will be your ultimate solution. We'll delve deep into a Python implementation that addresses this very problem. Stick with me as I unravel the magic behind each line of code!
The Problem:
Given a string s containing lowercase letters and question marks (?), and another string t of lowercase letters, the objective is to replace the ? in s such that the occurrences of t in s are maximized. Note that occurrences can overlap.
The Algorithm:
The primary solution hinges on two core functions: can_put and max_occurrences.
1.Function can_put(s, t, pos):
Purpose: To check if string t can be placed starting at position pos in string s.
1)For each character in t, the function checks whether it can either replace a ? or matches the respective character in s.
2)If it's feasible for all characters of t, the function returns True; otherwise, False.
2.Function max_occurrences(s, t):
Purpose: To compute the maximum number of occurrences of t in s after possible replacements of ?.
1)A list feasible_positions keeps track of all positions in s where t can potentially start.
2)The function first marks all feasible starting positions for t in s.
3)Using a sliding window approach of size equal to the length of t, the function checks if the substring of s starting from the current window position is feasible for placing t.
4)After the window has covered the entire string s, the function additionally counts the remaining feasible positions.
In Action:
The main execution of the code reads the strings s and t, computes the result with max_occurrences(s, t), and then prints the maximum possible occurrences.
Conclusion:
This Python implementation, with its efficient approach of pre-checking feasible positions combined with a sliding window technique, provides an elegant solution to the problem of maximizing string occurrences. Whether you're a coding enthusiast aiming to refine your skills or a professional seeking an optimal solution, this algorithm serves as an invaluable asset!
0 Comments