Inaccurate search
The task of finding a specific substring within a text is crucial, and most programming languages offer a standard library function to handle this. However, there are times when an approximate search is needed. We define the distance between two strings, (a) and (b), as the minimum number of operations required to transform string (a) into string (b). The permissible operations include replacing any character with another, inserting any character at any position, and deleting any character. For instance, the distance between the strings "cat" and "horse" is 2. Your task is to identify a substring within the given text that has a distance to the specified pattern not exceeding d.
Input
The first line contains the string in which the search is to be conducted. The string's length ranges from at least 1 character to no more than 2·10^6 characters. The second line contains the string representing the search pattern, with a length between 1 and 50 characters. Both strings consist of lowercase and uppercase Latin letters and digits. The final line contains an integer d (0 ≤ d ≤ 50), which is the maximum allowable distance between the search pattern and the desired substring.
Output
Output two integers: start and length, where start is the index of the first character of the found substring, and length is its length. Character indexing in the string begins at zero. If there are multiple valid solutions, you may output any one of them.