This challenge is about writing code to solve the following problem.
Given two strings A and B, your code should output the start and end indices of a substring of A with the following properties.
- The substring of A should also match some substring of B with up to one substitution of a single character in the string.
- There should be no longer substring of A that satisfies the first property.
A = xxxappleyyyyyyy B = zapllezzz
apple with indices
4 8 (indexing from 1) would be a valid output.
The score of your answer will be the sum of length of your code in bytes + the time in seconds it takes on my computer when run on strings A and B of length 1 million each.
Testing and input
I will run your code on two strings of length 1 million taken from the strings in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/
The input will be on standard in and will simply be two strings, separated by a new line.
Languages and libraries
You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also open source and freely available for Linux.
My machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code. As a consequence, only use easily available free software and please include full instructions how to compile and run your code.