# Finding Pattern Score in Python

I saw this problem in C++ on here and decided to try it in Python, which was much simpler. I've used the same problem blurb as in the link above, so they are consistent. I'm sure my code can be improved.

You are given 3 strings: text, pre_text and post_text. Let L be a substring of text. For each substring L of text, we define pattern_score as follows:

pre_text_pattern_score = highest n, such that first n characters of L are equal to the last n characters of pre_text and occur in the same exact order.

post_text_pattern_score = highest n such that last n characters of L are equal to the first n characters of post_text and occur in the same exact order.

pattern_score = pre_text_pattern_score + post_text_pattern_score. For example, if L = "nothing", pre_text = "bruno", and post_text = "ingenious", then

pre_text_pattern_score of L is 2 because the substring "no" is matched, and

post_text_pattern_score is 3 because the substring "ing" is matched.

pattern_score is 5 = 2 + 3 Your program should find a non-empty substring of text that maximizes pattern_score.

If there is a tie, return the substring with the maximal pre_text_pattern_score.

If multiple answers still have a tied score, return the answer that comes first lexicographically. Complete the definition of function string calculateScore(string text, string prefix,string suffix)

Constraints:

• text, pre_text, and post_text contain only lowercase letters ('a' - 'z')
• 1 <= |text| <= 50
• 1 <= |pre-text| <= 50
• 1 <= |post-text| <= 50 (where |S| denotes the number of characters in string S)

Sample case #1 text: "nothing" prefix: "bruno" suffix: "ingenious" Returns: "nothing" this is "no" from "bruno" and "ing" from "ingenious", so "nothing" is returned.

Sample case #2 text: "ab" prefix: "b" suffix: "a" Returns: "a"

def calculateScore(text, prefixString, suffixString):
result = {}
lenText = len(text)

while lenText > 0:
for i in range(len(text) + 1 - lenText):
substring = text[i:i + lenText]

# calc the pre_text_pattern_score
pre_text_pattern_score = min(len(prefixString), len(substring))

while pre_text_pattern_score > 0 and substring[:pre_text_pattern_score] != prefixString[-pre_text_pattern_score:]:
pre_text_pattern_score -= 1

# calc the post_text_pattern_score
post_text_pattern_score = min(len(suffixString), len(substring))

while post_text_pattern_score > 0 and substring[-post_text_pattern_score:] != suffixString[:post_text_pattern_score]:
post_text_pattern_score-= 1

# calculate the pattern_score
pattern_score = pre_text_pattern_score + post_text_pattern_score

if not pattern_score in result:
# resets the dictionary key
result[pattern_score] = []

result[pattern_score].append(substring)

lenText -= 1 # reduce lenText by 1

# store the highest key, so we can sort the right item to return
maximum_pattern_score = max(result.keys())

# make sure to sort the lexicographically lowest string of the highest key
result[maximum_pattern_score].sort()

# return the lexicographically highest key
return result[maximum_pattern_score][0]

• The problem says the last n chars of the prefix hve to match the begining of the substring L, So, in sample case #2 the end of the prefix should be highlighted: "habrahabr" Commented Nov 9, 2020 at 6:48

### Code Style

Remember to follow PEP 8 where you can. In particular, you should use snake_case rather than camelCase.

Be sure to use comments to explain why your steps are needed rather than just what your code does:

lenText -= 1 # reduce lenText by 1


It is reasonably clear what your code is doing, but you could comment to explain why you're doing this. I'd be tempted to rewrite your substring finding loop as:

# Iterate over all possible substrings of text
for start_index in range(0, len(text)):
for end_index in range(start_index + 1, len(text) + 1):
L = text[start_index:end_index]

# Stores the highest seen pattern score so far.

You then just need to check if your current score is strictly greater than the highest score seen so far and empty highest_substrings, then if you see a score greater than or equal to highest_score you add that substring to highest_substrings.