Finding all-but-one matches 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.
C++ time: O(n^2), extra space: O(1)

It takes 0.2s to complete the 15K data on my machine.

To compile it, use:

g++ -std=c++11 -O3 code.cpp -o code


To run it, use:

./code &lt; INPUT_FILE_THAT_CONTAINS_TWO_LINES_SPERATED_BY_A_LINE_BREAK


Explaination

The idea is simple, for string s1 and s2, we try to offset s2 by i:

s1: abcabcabc
s2: bcabcab


When offset is 3:

s1: abcabcabc
s2:    bcabcab


Then, for each offset i, we perform a dynamic programing scan on s1[i:] and s2. For each j, let f[j, 0] be the maximum length d such that s1[j - d:j] == s2[j - i - d: j - i]. Similarly, let f[j, 1] be the maximum length d such that strings s1[j - d:j] and s2[j - i - d:j - i] differ by at most 1 character.

So for s1[j] == s2[j - i], we have:

f[j, 0] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j]
f[j, 1] = f[j - 1, 1] + 1  // concat solution in f[j - 1, 1] and s1[j]


Otherwise:

f[j, 0] = 0  // the only choice is empty string
f[j, 1] = f[j - 1, 0] + 1  // concat solution in f[j - 1, 0] and s1[j] (or s2[j - i])


And:

f[-1, 0] = f[-1, 1] = 0 


Since we only need f[j - 1, :] to calculate f[j, :], only O(1) extra space is used.

Finally, the max length will be:

max(f[j, 1] for all valid j and all i)


Code

#include &lt;string&gt;
#include &lt;cassert&gt;
#include &lt;iostream&gt;

using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n1, n2;
    n1 = s1.size();
    n2 = s2.size();
    int max_len = 0;
    int max_end = -1;
    for(int i = 1 - n2; i &lt; n1; i++) {
        int f0, f1;
        int max_len2 = 0;
        int max_end2 = -1;
        f0 = f1 = 0;
        for(int j = max(i, 0), j_end = min(n1, i + n2); j &lt; j_end; j++) {
            if(s1[j] == s2[j - i]) {
                f0 += 1;
                f1 += 1;
            } else {
                f1 = f0 + 1;
                f0 = 0;
            }
            if(f1 &gt; max_len2) {
                max_len2 = f1;
                max_end2 = j + 1;
            }
        }
        if(max_len2 &gt; max_len) {
            max_len = max_len2;
            max_end = max_end2;
        }
    }
    assert(max_end != -1);
    // cout &lt;&lt; max_len &lt;&lt; endl;
    cout &lt;&lt; max_end - max_len + 1 &lt;&lt; " " &lt;&lt; max_end &lt;&lt; endl;
}