0
$\begingroup$

I'm trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an answer given in the question I linked above, but I want to try and improve my brute force algorithm.

Given a sequence $S = \{12345678910...n-1n | S \in \mathbb{Z}:\}$, the algorithm tries to compute the first index of a pattern $P$ in the string. For instance, $\mathrm{find}(P = 456) == 3$ as the sequence $456$ is located at index $3$. I have a very simple algorithm that generates a sequence till the substring is found, and then goes through the sequence to return the index of the substring. This algorithm is very slow for for large $N$ and I want to improve it:

def find_position(string):

    # Build a window of size len(string) and init from 1 -> m
    windowSize = len(string)
    window = [str(i) for i in range(1, windowSize + 1)]
    result = ''.join(window)

    # Loop till match
    while string not in result:

        # Remove front and add back
        window.append(str(int(window[-1]) + 1))

        # Join window and match
        result = ''.join(window)

    return result.index(string)

This algorithm is like a very basic Rabin-Karp without any hashing but just regular string matching. I am not too sure if adding a rolling hash would speed up this algorithm in any way because the slow aspect of the algorithm is generating and appending to the sequence and then checking if the string is contained in the window.

Any ideas on how to improve this algorithm?

$\endgroup$
3
  • $\begingroup$ You have to think about how your pattern $P$ can be generated. Is it generated by a single number? By two number? (ex: 324 can be generated by 23 24) By more numbers? Once you found the way to generate $P$ the earliest, only a little bit more work is required to get the index. I have no time to type out a full answer right now but maybe this can help you. $\endgroup$
    – Tassle
    Aug 31 '19 at 11:11
  • $\begingroup$ Hey I was trying to do this kind of thing for a long time now and I'm not too sure how to work through it. I can figure out how to check if a number can be generated by a single number or a two digit number but not much more than that. Do you have an idea on how to implement this kind of thing? $\endgroup$ Aug 31 '19 at 17:33
  • $\begingroup$ I'd suspect your bottleneck is generating the sequence in the first place, that you use some fancy search technique that is able to skip forward over stretches that can't contain the pattern won't make (much) of a difference. I'd use essentially a deterministic finite automaton on the sequence as it is generated, stopping as soon as it enters a final state (and marking places where it entered the initial state for determining the substring). $\endgroup$
    – vonbrand
    Sep 13 '19 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.