404395: GYM101492 L Approximate Search

Baidu, Inc. is a Chinese Web services company. Among the services they provide are web search and "Baidu Baike", a virtual, collaborative encyclopedia. Due to its remarkable growth and interesting set of challenges its employees need to solve on a daily basis, many young programmers aspire to get a internships or even full-time jobs at this company.

Emi "the Retired" Shouko will travel to Beijing next year and would like to get an interview there for an internship. He is now reading some books with common coding interview questions. He is especially interested in problems related to web search. One of the problems that has been drawing Emi's attention is as follows.

Given an N-character text and an M-character pattern, we would like to know if it is possible to find the pattern in the text. However, the pattern does not need to occur exactly. The search allows a maximum of K mismatches, where a mismatch can be any of the following: a substitution, an insertion, or the removal of a character.

Emi really liked this problem. He has had an idea and started coding his solution furiously. He knows you would love to join him for his trip to Beijing, so he wishes you to solve this problem as well.

The first row of the input has the integers M, N, and K. The second row contains a pattern made of M characters from 'a' to 'z'. The third row contains a text made of N characters from 'a' to 'z'.

• 1 ≤ M ≤ 10²
• 1 ≤ N ≤ 10⁶
• 1 ≤ K ≤ 20

If the pattern occurs in the text with at most K mismatches, print "S" (without the double quotes). Otherwise, print "N" (without the double quotes).

3 6 2
aed
abcdef

S

3 6 1
aed
abcdef

N

In the first example, if we remove the character 'b' and replace 'c' with 'e', the resulting text will be "aedef", which contains the pattern "aed". The same cannot be said if the maximum numbers of allowed mismatches were 1.