Hash function Dalla#4905
Professor Dall enjoys creating innovative "good" hash functions for strings. Recently, he introduced a new method in a paper. This method involves two parameters: a favorite string and a natural number , which is no greater than the length of . The hash function is applied to a string . The process begins by identifying all substrings of that are anagrams of . From these anagrams, the lexicographically largest substring A_1 and the smallest A_2 are chosen. Next, for each pair of substrings of length from A_1 and A_2, the number of characters that match in the same positions is counted. The sum of these counts is the desired hash value. If no anagram substrings of exist in , the hash function value is .
A substring is any consecutive sequence of characters within a string. An anagram is a string formed by rearranging the letters of another string.
The first line contains a natural number . The second line contains the string , whose length is a natural number not exceeding . The number does not exceed the length of . The third line contains the string , with a length not exceeding . It is guaranteed that the number of starting positions in for substrings that are anagrams of does not exceed . All strings consist solely of lowercase Latin letters.
Output the computed value of Dall's hash function.
Explanation for Example 1: The anagram substrings are , , (in order of appearance). The largest is , and the smallest is . Each string has substrings of length K = 2. The number of matches in and is , in and is , in and is , and in and is . This results in a total of matches.
Example 1