Benny And Two Strings
Practice
4.4 (19 votes)
Dynamic programming
Approved
Medium Hard
String
Problem
84% Success 255 Attempts 50 Points 2s Time Limit 256MB Memory 1024 KB Max Code

Benny is given two strings S and T. The length of the string S is N and the length of the string T is M respectively.

Also, imagine that alphabets are cyclic in nature: a-b-c-…-x-y-z-a-b.. and so on. The distance between two letters is the minimal distance between them in the alphabet cycle. For example, distance between ‘a’ and ‘c’ is 2, when distance between ‘b’ and ‘z’ is 2.

Let’s call the process transformation when one letter turns to another one. The cost of the transformation is the distance between these letters.

She may perform some transformations in string T, but the total cost of these transformations should not exceed K.

Now, she wants to make a string T from the given string T such that S appears the most times in T as a substring.

For example, abc is a substring of ababc but bac is not a substring of ababc.

Output the maximal numbers of occurrences of string S in T after making transformations with total cost not more that K.

Input format

The first line contains three space separated integers N, M and K.

The next two lines contain strings S and and T respectively.

Output format

Print in a single line an answer to the problem.

Constraints

  • 1N, M\(200\)
  • 0K\(500\)

Note
Strings contain only lowercase English letters.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:20
3 votes
Tags:
MathematicsApprovedEasyMathematicsMathamatics
Points:50
Tags:
MathematicsHardApprovedRecruit
Points:20
22 votes
Tags:
ApprovedEasyMathOpenSorting