Inaccurate search#2082
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, and , as the minimum number of operations required to transform string into string . 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 . Your task is to identify a substring within the given text that has a distance to the specified pattern not exceeding .
The first line contains the string in which the search is to be conducted. The string's length ranges from at least character to no more than 2 \cdot 10^6 characters. The second line contains the string representing the search pattern, with a length between and characters. Both strings consist of lowercase and uppercase Latin letters and digits. The final line contains an integer (0 \leq d \leq 50), which is the maximum allowable distance between the search pattern and the desired substring.
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.
Example 1
Example 2