18
1
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.
For example:
A = xxxappleyyyyyyy
B = zapllezzz
The substring apple
with indices 4 8
(indexing from 1) would be a valid output.
Score
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.
You need more absolute scoring definition. Running time on your computer doesn't sound like a good scoring method. – mbomb007 – 2015-02-27T15:24:39.363
7@mbomb007 It's the only sensible way to measure code speed and is the one always used in fastest code competitions on PPCG! People normally post their score on their own computer in their answer and wait for the OP to then produce a definitive score. It is 100% unambiguous at least. – None – 2015-02-27T15:25:43.423
5@mbomb007 that is a very widely used scoring method for fastest code. – Optimizer – 2015-02-27T15:27:33.777
if(hash(str1 == test1 && str2 == test2)) print("100,150") else ..
-- thoughts? – John Dvorak – 2015-02-27T15:39:56.6772@FryAmTheEggman In the very unlikely event of a tie, the first answer wins.
appley
needs two substitutions to matchapllez
. Maybe you missed that it isapll
in B and notappl
? – None – 2015-02-27T19:37:11.283