The Missing Number - Version 2 Background:

This question is a remix of the one that I made previously on this forum. The only difference with this one is: the range is significantly larger, AND dynamic. Details below!

Also, I'm typing this question incredibly quickly, so if there are any grammatical errors, I do apologize and ask if anyone would edit the question to clear any vagueness. Nonetheless, the original question is posted here: The Missing Number Revised

Question:

Given a minimum bound M, a maximum bound N, and a String of randomly concatenated integers [min, max), min (M) to max (N) exclusive, there is a number missing in the sequence. Your job is to write a program that will calculate this missing number. 

Doing this problem by hand on smaller Strings, such as examples 1 and 2 below are obviously very easy. Conversely, computing a missing number on incredibly large datasets involving three-digit, four-digit, or more numbers would be incredibly difficult. The idea behind this problem is to construct a program that will do this process FOR you.

Important Information:

One thing that appeared as rather confusing when I posted this problem last night was: what exactly a missing number is defined as. A missing number is the number INSIDE of the range specified above; NOT necessarily the digit. In example 3, you will see that the missing number is 7, even though it appears in the sequence. There are 3 places the DIGIT 7 will appear in a series of [0, 30): “7”, “17”, and “27”. Your objective is to differentiate between these, and discover that 7 is the missing NUMBER (inside of example 3). In other words, the tricky part lies in finding out which sequences of digits are complete and which belong to other numbers.

Another very important factor in this: there are some input situations where there are multiple solutions! Your job will be to print out ALL numbers that are missing in the sequence. I cannot provide insight as to WHY they have multiple solutions; I only know they may exist. 

Input:

The input is a single Integer T: the amount of test cases.

For each test case, there is an Integer M: the minimum number in the sequence, another Integer N: the maximum number in the sequence (thus M &lt; N at ALL times), a String S, containing integers from M to N - 1 inclusive, or M to N exclusive (in other words, [M, N)). These integers, as stated above, are scrambled up to create a random sequence. There are NO delimiters (“42, 31, 23, 44”), or padding 0’s (003076244029002); the problems are exactly as described in the examples. 

As stated above, M is ALWAYS lower than N, and the maximum range of numbers is &lt; 100,000. |N - M|.

Winning Criteria:

Whoever has the fastest, and lowest memory usage will be the winner. In the miraculous event that a time ties, lower memory will be used for the time breaker. Please list Big O if you can!

Examples:

(Examples 1-6 are just for demonstration. Your program needn't to handle them.)

Here is a pastebin link of the examples.

TEST DATA

Please keep in mind the way you're to read in the data: Digit D represents how MANY test cases there are, the next lines will follow with integers M and N, then String S. I just wanted to clear it up. I also apologize for the incredibly large pastebin. Good luck!

Data: Test Data - Github repository
Clean -  Complexity Unknown
Currently works, explanation and further optimization in progress
module main
import StdEnv, StdLib, System.IO

:: Position :== [Int]
:: Positions :== [Position]
:: Digit :== (Char, Int)
:: Digits :== [Digit]
:: Number :== ([Char], Positions)
:: Numbers :== [Number]
:: Complete :== (Numbers, Positions)

decouple =: snd o unzip

//lcouple :: (.a -&gt; .b) (.a, .c) -&gt; (.b, .c)
lcouple fn (arg, oth) :== (fn arg, oth)

getCases :: Int *World -&gt; ([(String, [[Char]])], *World)
getCases n world
    # (range, world)
        = evalIO getLine world
    # range
        = fromString range
    # spacePos
        = elemIndex ' ' range
    | isNothing spacePos
        = abort &quot;invalid input, expected space in range\n&quot;
    # (a, b)
        = splitAt (fromJust spacePos) range
    # (a, b)
        = (toInt (toString a), toInt (toString (tl b)))
    # numbers
        = [(fromString o toString) number \\ number &lt;- [a..(b-1)]]
    # (string, world)
        = evalIO getLine world
    | n &gt; 1
        # (cases, world)
            = getCases (n - 1) world
        = ([(string, numbers) : cases], world)
    = ([(string, numbers)], world)
        
singletonSieve :: Complete -&gt; Complete
singletonSieve (list, sequence)
    | sequence_ == sequence
        = reverseSieve (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles 
        = [hd pos \\ (_, pos) &lt;- list | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter notInOtherSingle)) list
    where
        notInOtherSingle :: Position -&gt; Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((&lt;&gt;) pos) singles)))
    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles

reverseSieve :: Complete -&gt; Complete
reverseSieve (list, sequence)
    | sequence_ == sequence
        = (list, sequence)
    = (list_, sequence_)
where
    singles :: Positions
    singles
        = [hd pos \\ pos &lt;- [[subSeq \\ subSeq &lt;- sequence | isMember subSeq p] \\ (_, p) &lt;- list] | length pos == 1]
        //= [hd pos \\ pos &lt;- | length pos == 1]
    list_ :: Numbers
    list_
        = map (app2 (id, filter (\b_ = (notInOtherSingle b_) &amp;&amp; (hasContiguousRun b_)))) list
    where
        notInOtherSingle :: Position -&gt; Bool
        notInOtherSingle pos
            = not (isAnyMember pos (flatten (filter ((&lt;&gt;) pos) singles)))
        hasContiguousRun :: Position -&gt; Bool
        hasContiguousRun pos
            //= any (any (isPrefixOf pos) o tails) sequence_
            = and [isMember p (flatten sequence_) \\ p &lt;- pos]
            
    sequence_ :: Positions
    sequence_
        = foldr splitSequence sequence singles
    
splitSequence :: Position Positions -&gt; Positions
splitSequence split sequence
    = flatten (map newSplit (map (span (not o ((flip isMember) split))) sequence))
where
    newSplit :: (Position, Position) -&gt; Positions
    newSplit ([], b)
        # b
            = drop (length split) b
        | b &gt; []
            = [b]
        = []
    newSplit (a, b)
        # b
            = drop (length split) b
        | b &gt; []
            = [a, b]
        = [a]

indexSubSeq :: [Char] Digits -&gt; Positions
indexSubSeq _ []
    = []
indexSubSeq a b
    # remainder
        = indexSubSeq a (tl b)
    | isPrefixOf a (map fst b)
        = [[i \\ (_, i) &lt;- take (length a) b] : remainder]
        //= [[i \\ _ &lt;- a &amp; (_, i) &lt;- b] : remainder]
    = remainder
    
missingNumber :: String [[Char]] -&gt; [[Char]]
missingNumber string numbers
    # string
        = [(c, i) \\ c &lt;-: string &amp; i &lt;- [0..]]
    # locations
        = [(number, indexSubSeq number string) \\ number &lt;- numbers]
    # digits
        = [length (indexSubSeq [digit] [(c, i) \\ c &lt;- (flatten numbers) &amp; i &lt;- [0..]]) \\ digit &lt;-: &quot;0123456789-&quot;]
    # missing
        = flatten [repeatn (n - length i) c \\ n &lt;- digits &amp; (c, i) &lt;- [(digit, indexSubSeq [digit] string) \\ digit &lt;-: &quot;0123456789-&quot;]]
    # (answers, _)
        = until (\e = e == singletonSieve e || length [(a, b) \\ (a, b) &lt;- fst e | length b == 0 &amp;&amp; isMember a (candidates missing)] &gt; 0) singletonSieve (locations, [indexList string])
    # answers
        = filter (\(_, i) = length i == 0) answers
    = filter ((flip isMember)(candidates missing)) ((fst o unzip) answers)
where
    candidates :: [Char] -&gt; [[Char]]
    candidates chars
        = moreCandidates chars []
    where
        moreCandidates :: [Char] [[Char]] -&gt; [[Char]]
        moreCandidates [] nums
            = removeDup (filter (\num = isMember num numbers) nums)
        moreCandidates chars []
            = flatten [moreCandidates (removeAt i chars) [[c]] \\ c &lt;- chars &amp; i &lt;- [0..]]
        moreCandidates chars nums
            = flatten [flatten [moreCandidates (removeAt i chars) [ [c : num] \\ num &lt;- nums ]] \\  c &lt;- chars &amp; i &lt;- [0..]]
            
Start world
    # (number, world)
        = evalIO getLine world
    # (cases, world)
        = getCases (toInt number) world
    =  flatlines[flatten(intersperse [', '] (missingNumber string numbers)) \\ (string, numbers) &lt;- cases]

Try it online!